Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.
Example 1:
Input: [23, 2, 4, 6, 7], k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.
brute force
早上来一发。
这题我先用了O(n2)的brute force解法，先AC为敬；玛德，corner case真多，比如n, k, nums是不是0。
//sums up to n*k where n is also an integer, can k be zero(YES)?
public boolean checkSubarraySum(int[] nums, int k) {
if (nums.length < 2) return false;
if (checkAllZero(nums)) return true;
if (k == 0) return checkAllZero(nums);
for (int i = 0; i < nums.length - 1; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
if (j - i > 0 && sum % k == 0) return true;
}
}
return false;
}
private boolean checkAllZero(int[] nums) {
for (Integer i : nums) {
if (i != 0) return false;
}
return true;
}
One pass
我再想想，这题肯定有O(n)解法的。O(n)一般就是HashMap，但是我只能想到map.get(i) - k，仔细一想没什么意义。
我看了高票solution，又是非常tricky：
public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>(){{put(0,-1);}};;
int runningSum = 0;
for (int i=0;i<nums.length;i++) {
runningSum += nums[i];
if (k != 0) runningSum %= k;
Integer prev = map.get(runningSum);
if (prev != null) {
if (i - prev > 1) return true;
}
else map.put(runningSum, i);
}
return false;
}
就是看迄今为止的mod值，如果sum[i]和sum[j]的mod值相同，那就说明nums(i , j ] mod k肯定等于0(注意不是nums[i , j ]。所以j至少要比i大2，因为有有at least 2 contigious numbers的限制)。思想就是这么个思想，但他这个代码其实巧妙地处理了很多corner case，一般人看不出来，日。比如一开始put(0,-1)进入，就是说如果在第2位找到了mod == 0的数，那就 1 -（-1）>1，return true。所以你不能put(0,0)。也不能put(0,-999)。
还有，他用了滚动的runningSum，每次都mod k之后加到原来的runningSum上，这样runningSum同时又可以作为mod(作为map 的key)，真是巧妙。
我试着把mod抽出来，发现不行的，因为mod会一直等于同一个数，很快就return true了。
下面的代码不能AC:
public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>() {{
put(0, -1);
}};
int runningSum = 0;
int mod = -1;
for (int i = 0; i < nums.length; i++) {
runningSum += nums[i];
if (k != 0) mod = runningSum % k;
Integer prev = map.get(mod);
if (prev != null) {
if (i - prev > 1)
return true;
} else map.put(mod, i);
}
return false;
}
这种题一定要一次想到底，画个图。中途放弃再看就会想不下去，很有挫败感。
