BiruLyu
6/28/2017 - 11:15 PM

## 523. Continuous Subarray Sum(Pigeonhole).java

``````public class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
if (nums == null || nums.length < 1) return false;
int n = nums.length;
//if (k != 0 && n >= 2 * Math.abs(k)) return true; //容斥原理[0,1,1,2,2,3,3,4,4,...,2k-1,2k-1]

HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(0, -1); // if 0 appears in any position, except 0, return true
int prefixSum = 0;
for (int i = 0; i < n; i++) {
prefixSum += nums[i];
if (k != 0) prefixSum %= k;
Integer pre = map.get(prefixSum);
if (pre != null) {
if (i - pre > 1) return true;
} else {
map.put(prefixSum, i);
}
}
return false;
}
}``````
``````public class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
if (nums == null || nums.length < 1) return false;
int n = nums.length;
if (k != 0 && n >= (long)2 * Math.abs(k)) return true; //容斥原理[0,1,1,2,2,3,3,4,4,...,2k-1,2k-1]

HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(0, -1); // if 0 appears in any position, except 0, return true
int prefixSum = 0;
for (int i = 0; i < n; i++) {
prefixSum += nums[i];
if (k != 0) prefixSum %= k;
Integer pre = map.get(prefixSum);
if (pre != null) {
if (i - pre > 1) return true;
} else {
map.put(prefixSum, i);
}
}
return false;
}
}``````