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
早上來一發(fā)。
這題我先用了O(n2)的brute force解法，先AC為敬霎匈；瑪?shù)掳琧orner 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酣藻，仔細(xì)一想沒什么意義曹洽。
我看了高票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怕轿，因?yàn)橛杏衋t least 2 contigious numbers的限制)偷崩。思想就是這么個(gè)思想，但他這個(gè)代碼其實(shí)巧妙地處理了很多corner case撞羽，一般人看不出來阐斜，日。比如一開始put(0,-1)進(jìn)入诀紊，就是說如果在第2位找到了mod == 0的數(shù)谒出，那就 1 -（-1）>1，return true邻奠。所以你不能put(0,0)笤喳。也不能put(0,-999)。
還有碌宴，他用了滾動(dòng)的runningSum杀狡，每次都mod k之后加到原來的runningSum上，這樣runningSum同時(shí)又可以作為mod(作為map 的key)贰镣，真是巧妙呜象。
我試著把mod抽出來，發(fā)現(xiàn)不行的碑隆，因?yàn)閙od會(huì)一直等于同一個(gè)數(shù)董朝，很快就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;
}
這種題一定要一次想到底干跛，畫個(gè)圖。中途放棄再看就會(huì)想不下去祟绊，很有挫敗感楼入。
