05 August 2008
前缀和 + HashSet
具体的，使用 HashSet 来保存出现过的值。
让循环从 2 开始枚举右端点（根据题目要求，子数组长度至少为 2），每次将符合长度要求的位置的取余结果存入 HashSet。
如果枚举某个右端点 j 时发现存在某个左端点 i 符合要求，则返回 True。
时间复杂度：O(n)
空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
int len = nums.length;
int[] sum = new int[len + 1];
for (int i = 1; i <= len; i++) {
sum[i] = sum[i - 1] + nums[i - 1];
}
HashSet<Integer> set = new HashSet<>();
for (int i = 2; i <= len; i++) {
set.add(sum[i - 2] % k);
if (set.contains(sum[i] % k)) {
return true;
}
}
return false;
}
}