使数组和能被P整除Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给你一个正整数数组 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 <= 105
- 1 <= nums[i] <= 109
- 1 <= p <= 109
# 思路
定义前缀和数组
# 解法
class Solution {
public int minSubarray(int[] nums, int p) {
// 思路：使用前缀和 s[] (s[0] = 0[表示前0 个元素])的方法
// 首先得到数组和，对 p 进行取余，查看余数 x;
// 如果 x = 0，那就更好，直接返回 0；
// 如果 x ≠ 0，那么就要去掉一连串元素，使得 x = 0
// 这里面的一连串元素刚好是（某两个前缀和之差）
// 思想就是，两个前缀和之差的对 p 进行取余，等于 x, 那么刚好去除他们，得到 x = 0，满足题意
// 综上，(s[right] - s[left]) % p = x, 即 s[right] − s[left] ≡ x (mod p)
// s[right] - x = s[left] (mod p)
// 为了保证左项不为负数，等价于下面的式子：
// ((s[right] - x) % p + p) % p = s[left] % p (＊＊＊)
// 题目转化就是找到这个 right 和 left，且 right - left 最小, 按照如上式求解
int len = nums.length;
// 定义前缀和数组
int [] s = new int[len + 1];
for(int i = 1; i <= len; i++){
s[i] = (s[i - 1] + nums[i - 1]) % p;
}
// 找到数组和的取余数
int x = s[len];
// 等于 0 就直接返回
if(x == 0){
return 0;
}
// 最大返回 n 次
int ans = len;
// 使用 hashMap 来存，方便查找符合条件的
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
// 根据（＊＊＊） 求解
for(int i = 0; i <= len; i++){
// s[right]
map.put(s[i], i);
// 找已存入的，即 s[left]
// 不存在就返回 - len, 那么 i - j >= n
int j = map.getOrDefault((s[i] - x + p) % p, -len);
ans = Math.min(ans, i - j);
}
// 因为不能全部删除，所以肯定是小于 n
return ans < len ? ans: -1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# 总结
- 分析出几种情况，然后分别对各个情况实现
