Medium
不理解为什么这种简单题是medium, 而很多比较复杂的graph，dp的题也是medium……
brute force也能过 time: O(n2) space: O(1)
class Solution {
public int subarraySum(int[] nums, int k) {
if(nums == null || nums.length == 0){
return 0;
}
int count = 0;
for (int i = 0; i < nums.length; i++){
int sum = 0;
sum += nums[i];
if (sum == k){
count++;
}
for (int j = i + 1; j < nums.length; j++){
sum += nums[j];
if (sum == k){
count++;
}
}
}
return count;
}
}
另一种preSum的解法，时间O(n) 空间O(n)
这个方法第一眼看上去不是很好理解，要具体想一想.
其实就是我们从左到右遍历数组记录下当前subarray的sum出现的次数，然后存到preSum这个map里。当我们每次得到一个sum时，去搜索preSum里面有没有sum - k这个数。如果有，就说明我们有一段子数列的和是sum - k, 有一段子数列的和是k, 最后才有可能得到一段和为sum的子数列。而且出现的次数就代表有多种可能，每种可能我们都能得到对应的和为sum的子数列。
至于为什么一开始要在preSum里面存入(0,1),看一个例子：
比如input = [1,1,1], k = 2
当我们加到前两个1的和等于2时，我们会去preSum map里面搜索有没有等于2-2=0(sum - k)这个key, 一开始如果不把（0，1）放进去，就会少算这种情况。
image.png
class Solution {
public int subarraySum(int[] nums, int k) {
if(nums == null || nums.length == 0){
return 0;
}
int res = 0, sum = 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)){
res += preSum.get(sum - k);
}
preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
}
return res;
}
}
