目标
给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。
请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。
子数组 定义为原数组中连续的一组元素。
示例 1：
输入：nums = [3,1,4,2], p = 6
输出：1
解释：nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。示例 2：
输入：nums = [6,3,5,2], p = 9
输出：2
解释：我们无法移除任何一个元素使得和被 9 整除，最优方案是移除子数组 [5,2] ，剩余元素为 [6,3]，和为 9 。示例 3：
输入：nums = [1,2,3], p = 3
输出：0
解释：和恰好为 6 ，已经能被 3 整除了。所以我们不需要移除任何元素。示例 4：
输入：nums = [1,2,3], p = 7
输出：-1
解释：没有任何方案使得移除子数组后剩余元素的和被 7 整除。示例 5：
输入：nums = [1000000000,1000000000,1000000000], p = 3
输出：0说明：
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9
- 1 <= p <= 10^9
思路
有一个正整数数组 nums，需要移除一个最短子数组（可以为空），使得剩余元素的和能被 p 整除，返回移除的最短子数组长度，如果无法满足返回 -1。
计算数组和，求出余数 rem，使用哈希表 lastIndex 记录前缀和余数的最大下标，根据当前前缀和的余数，计算需要保留的前缀数组 [0, lastIndex.get((curRem - rem + p) % p)]，计算得到需要减去的子数组 [lastIndex.get((curRem - rem + p) % p) + 1, i] 它的和模 p 余 rem，取长度的最小值即可。
代码
/**
* @date 2025-11-30 10:41
*/
public class MinSubarray1590 {
public int minSubarray(int[] nums, int p) {
int n = nums.length;
long sum = 0;
for (int num : nums) {
sum += num;
}
int rem = (int) (sum % p);
if (rem == 0) {
return 0;
}
Map<Integer, Integer> lastIndex = new HashMap<>();
lastIndex.putIfAbsent(0, -1);
int curRem = 0;
int res = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
curRem = (curRem + nums[i]) % p;
int prev = (p + curRem - rem) % p;
res = Math.min(res, i - lastIndex.getOrDefault(prev, -n));
lastIndex.put(curRem, i);
}
return res == n ? -1 : res;
}
}
性能
