这是weekly test30的第二题。
brute force
用brute force的话就是从每个数字向前或向后遍历，减去当前值，等于0就count++，不需要中断，因为有可能000000，k=0这种情况，而且什么时候中断也不好判断。。
Time 是 O(n^2)。用Java能过，python好像会TLE。
public int subarraySum(int[] nums, int k) {
int res = 0;
if (nums == null || nums.length == 0) return 0;
for (int i = 0; i < nums.length; i++) {
int temp = k;
for (int j = i; j >= 0; j--) {
temp = temp - nums[j];
if (temp == 0) res++;
}
}
return res;
}
O(n)解法
类似sliding window。挺难理解的，但是似乎是routine。
public int subarraySum(int[] nums, int k) {
int sum = 0, result = 0;
Map<Integer, Integer> preSum = new HashMap<>();
preSum.put(0, 1);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (preSum.containsKey(sum - k)) {
result += preSum.get(sum - k);
}
preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
}
return result;
}
ref:
https://discuss.leetcode.com/topic/87838/share-my-o-n-time-solution
02052017
今天发现这题有了Editorial Solution。
Approach #1 Brute Force [Time Limit Exceeded]
Approach #2 Using Cummulative sum [Accepted]
Approach #3 Without space [Accepted]
Approach #4 Using hashmap [Accepted]
Approach #1用了三重循环，定义start，end，再用一重从start到end。。O(n3)。会TLE。
Approach #2用了累加，定义一个sum[nums.length+1]长度的数组，记载着到目前nums[i]为止的数的和。那么nums[i , j ]之间的和就是sum[j+1] - sum[i]，很好理解，但是坐标要想清楚，sum比nums多1的。这本质上跟Approach #1一样，只是Approach #1每次都手动加一遍nums[i , j ]的数，而这个方法用了O(n)space避免重复计算。
Approach #3就是上面提到的brute force方法。找一个particular start point and iterate the end point.
Approach #4就是上面说的第二种方法。很巧妙。这方法的基于一个idea：sum[j] - sum[i] == k的话，nums[i , j ]之间数字的和就是k。比如sum[j]跟sum[i]是一样的，那中间这段加起来就是0。其实跟approach 1和2也是类似的思想啊。 比如难懂的是
count += map.get(sum - k)，这个要这么理解，就是如果sum - k多次等于一个值，那么前面每一个nums[i]位置到这里的subarray 都算是一个count，所以要记得之前有多少个相同的值。
下图，k = 7 。恰好有多次都等于14，说明几个14之间都差0。其实不等于14也行，比如，等于10，那么就跟第一个数字之间差7；等于21，那么就跟14之间差7。
