使数组和能被 P 整除【LC1590】
给你一个正整数数组
nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被p整除。 不允许 将整个数组都移除。请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回
-1。子数组 定义为原数组中连续的一组元素。
这种只差一点的感觉 真难受
- 思路
- 因此我们可以将前缀和放入哈希表中，哈希表存放前缀和及其对应的下标，然后对于每个
right，查找是否有符合的left，有则更新最小长度 - 实现
为了防止越界，前缀和数组记录对p取余的结果
class Solution { public int minSubarray(int[] nums, int p) { int n = nums.length, ans = n; var s = new int[n + 1]; for (int i = 0; i < n; ++i) s[i + 1] = (s[i] + nums[i]) % p; int x = s[n]; if (x == 0) return 0; // 移除空子数组（这行可以不要） var last = new HashMap<Integer, Integer>(); for (int i = 0; i <= n; ++i) { last.put(s[i], i); // 如果不存在，-n 可以保证 i-j >= n int j = last.getOrDefault((s[i] - x + p) % p, -n); ans = Math.min(ans, i - j); } return ans < n ? ans : -1; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/make-sum-divisible-by-p/solutions/2158435/tao-lu-qian-zhui-he-ha-xi-biao-pythonjav-rzl0/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
