[每日一题]1590.使数组和能被 P 整除
1590. 使数组和能被 P 整除 给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。
请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。
子数组 定义为原数组中连续的一组元素。
输入：nums = [3,1,4,2], p = 6 输出：1 解释：nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。
输入：nums = [6,3,5,2], p = 9 输出：2 解释：我们无法移除任何一个元素使得和被 9 整除，最优方案是移除子数组 [5,2] ，剩余元素为 [6,3]，和为 9 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= p <= 109
Solutions
class Solution {
public int minSubarray(int[] nums, int p) {
final int MAX_VALUE = 1_000_000_001;
int length = nums.length, remainder = 0;
// length 存储数组的长度，remainder 为除以 p 的余数
for (int num : nums) {
remainder = (remainder + num) % p;
// 先求出数组的和，注意用 Stream API 可能出现越界情况
}
if (remainder == 0) {
return 0; // 如果已经满足条件，则不需要删除任何元素，直接返回 0
}
int current = 0, result = MAX_VALUE;
// current 实际上是取余后的前缀和，result 存储结果
Map<Integer, Integer> numberMap = new HashMap<>();
numberMap.put(0, -1);
// [注意] 这一步很关键，当数组没有元素时，余数为 0，由于还没有开始遍历数组，位置为 -1
for (int i = 0; i < length; ++i) {
current = (current + nums[i]) % p; // 更新 current，即前缀和
numberMap.put(current, i);
// 更新哈希表中 数组从开始到现在的前缀和除以 p 的余数的位置 i
int last = numberMap.getOrDefault((current + p - remainder) % p, -MAX_VALUE);
// 这一步也非常关键，找到元素和的余数为 (current + p - remainder) % p 的子数组开始位置
// [注意] 这里需要注意为什么是 (current + p - remainder) % p
// 因为子数组要满足元素和 与 整个数组 nums 元素和 mod p 同余
// 考虑到前缀和结束位置 i 时，余数为 current，那么子数组开始时，应该与 current - remainder 同余
// 注意到我们将余数标准化为正数，位于区间 [0, p)，结合 Java 中 % 运算的性质，得出结论
result = Math.min(result, i - last);
}
return result == length ? -1 : result;
// 如果要将数组所有元素删除，则没有任何符合条件的删除方法，因此返回 -1；否则返回 result
}
}
Ideas
-
前缀和 + 哈希表
我们可以先求出数组 nums 所有元素之和模 p 的值，记为 k。如果 k 为 0，说明数组 nums 所有元素之和就是 p 的倍数，直接返回 0 即可。
如果 k 不为 0，我们需要找到一个最短的子数组，使得删除该子数组后，剩余元素之和模 p 的值为 0。
我们可以遍历数组 nums，维护当前的前缀和模 p 的值，记为 cur。用哈希表 last 记录每个前缀和模 p 的值最后一次出现的位置。
如果当前存在一个以
nums[i]结尾的子数组，使得删除该子数组后，剩余元素之和模 p 的值为 0。也就是说，我们需要找到此前的一个前缀和模 p 的值为 target 的位置 j，使得(target+k−cur) mod p=0。如果找到，我们就可以将 j+1 到 i 这一段闭区间子数组nums[j+1,..i]删除，使得剩余元素之和模 p 的值为 0。因此，如果存在一个
target=(cur−k+p) mod p，那么我们可以更新答案为min(ans,i−j)。接下来，我们更新last[cur]的值为 i。继续遍历数组 nums，直到遍历结束，即可得到答案。