1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
int sum = 0;
Map<Integer, Integer> modulo = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
int currModulo = sum % k;
if (i > 0 && currModulo == 0) {
return true;
}
if (i - modulo.getOrDefault(currModulo, i) >= 2) {
return true;
}
modulo.put(currModulo, modulo.getOrDefault(currModulo, i));
}
return false;
}
}
|
这里不是记录prefix sum, 而是prefix modulo. 如果之前出现过一个prefix sum的modulo和我们现在的位置的modulo相同并且从而产生的subarray长度大于等于2时, 我们就返回true, 否则就把当前的modulo放入map中. 需要注意的是如果我们的modulo已经在map中, 只是因为map中的modulo挨着我们, 此时我们要保留map中该modulo的位置而不是更新到我们当前的位置. map中记录的是各个modulo出现的最左边的位置.
时间复杂度: O(n)
空间复杂度: O(k) modulo一共就k种情况.
