1590. 使数组和能被 P 整除
给你一个正整数数组 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解答：哈希表+取模
class Solution {
public int minSubarray(int[] nums, int p) {
// 计算整个数组元素之和对p的余数
int x = 0;
for (int num : nums) {
// 累加数组元素，计算余数
x = (x + num) % p;
}
// 如果整个数组元素之和能够被p整除，直接返回0
if (x == 0) {
return 0;
}
// 定义哈希表，记录余数对应的下标
Map<Integer, Integer> index = new HashMap<Integer, Integer>();
// 定义余数y和结果res，初始化res为数组长度
int y = 0, res = nums.length;
for (int i = 0; i < nums.length; i++) {
// 记录当前余数对应的下标
index.put(y, i);
// 计算下一个余数
y = (y + nums[i]) % p;
// 如果出现了一个余数，它减去x之后的余数之前出现过
if (index.containsKey((y - x + p) % p)) {
// 更新结果res
res = Math.min(res, i - index.get((y - x + p) % p) + 1);
}
}
// 返回结果，如果res等于数组长度说明找不到满足条件的子数组，返回-1
return res == nums.length ? -1 : res;
}
}
