力扣560.和为K的子数组

题目介绍

题解

前缀和+哈希表（两数之和）：

代码如下：

class Solution {public int subarraySum(int[] nums, int k) {int n = nums.length;int[] s = new int[n + 1];for (int i = 0; i < n; i++) {s[i + 1] = s[i] + nums[i];}int res = 0;Map<Integer, Integer> map = new HashMap<>(n + 1); // 设置容量可以快 2msfor (int he : s) {res += map.getOrDefault(he - k, 0);map.put(he, map.getOrDefault(he, 0) + 1); // map[he]++}return res;}
}

错解：这种方法只适用于数组中所有元素都是正数的情况。 当数组中包含负数时，滑动窗口就不能保证正确性了。 例如，nums = [-1, -1, 1] 和 k = 0，你的算法会漏掉 [-1, -1, 1] 这个子数组。

class Solution {public int subarraySum(int[] nums, int k) {int res = 0, len = nums.length, l = 0, sum = 0;for (int r = 0; r < len; r++) {sum += nums[r];if (sum == k) {res++;}while (sum > k && l <= r) {sum -= nums[l++];if (sum == k) {res++;}}}return res;}
}