560.|560. Subarray Sum Equals K 560.SubarraySumEqualsK

【560.|560. Subarray Sum Equals K】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 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; } }