Leetcode560. 和为 K 的子数组

Leetcode560. 和为 K 的子数组

题目：
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2
1
2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2
1
2

题解：
前缀和 + 哈希表
我们定义 $\text{pre}[i]$ 为 $[\mathrm{0..}i]$ 里所有数的和，则 $\text{pre}[i]$ 可以由 $\text{pre}[i-1]$ 递推而来，即：

$\text{pre}[i]=\text{pre}[i-1]+\text{nums}[i]$

那么【$[j..i]$ 这个子数组和为 $k$ 】这个条件我们可以转化为

$\text{pre}[i]-\text{pre}[j-1]==k$

简单移项可得符合条件的下标 $j$ 需要满足

$\text{pre}[j-1]==\text{pre}[i]-k$

所以我们考虑以 $i$ 结尾的和为 $k$ 的连续子数组个数时只要统计有多少个前缀和为 $\text{pre}[i]-k$的 $\text{pre}[j]$ 即可。我们建立哈希表 $\text{mp}$，以和为键，出现次数为对应的$\text{pre}[j]$的下标范围是 $0\le j\le i$ 。同时，由于$\text{pre}[i]$的计算只与前一项的答案有关，因此我们可以不用建立 $\text{pre}$ 数组，直接用 $\text{pre}$ 变量来记录 $pre[i-1]$ 的答案即可。

java代码：

  /**
     * @param nums
     * @param k
     * @return
     */
    public static int subarraySum(int[] nums, int k) {
        int count = 0, pre = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];

            if (map.containsKey(pre - k)) {
                count += map.get(pre - k);
            }
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return count;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19