Medium FB tag
naive方法：O(n2)
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
if (nums == null || nums.length == 0){
return false;
}
for (int i = 0; i < nums.length; i++){
int sum = nums[i];
for (int j = i + 1; j < nums.length; j++){
sum += nums[j];
if (k == 0){
return sum == 0;
} else {
if (sum % k == 0){
return true;
}
}
}
}
return false;
}
}
另一种是preSum的方法,不过这里要利用到余数的一些特性：
(a+(n*x))%x is same as (a%x),
就是如果preSum[6] % k = 1, 然后preSum[8] / k = 1, 又因为这个数列都是非负数，这种情况可以说明sum[7, 8] (inclusively)能被k整除。
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
if (nums == null || nums.length == 0){
return false;
}
// [0,0]
// 0
int preSum = 0;
Map<Integer, Integer> preSumIndexMap = new HashMap<>();
//[6,1,2,3] k=6 , when i = 0 won't return true coz prev = -1 and i = 0 so i - prev = 1 < 1
preSumIndexMap.put(0, -1);
for (int i = 0; i < nums.length; i++){
preSum += nums[i];
if (k != 0){
preSum %= k;
}
if (preSumIndexMap.containsKey(preSum)){
int prev = preSumIndexMap.get(preSum);
if (i - prev > 1){
return true;
}
} else {
preSumIndexMap.put(preSum, i);
}
}
return false;
}
}
