题解 | 「力扣」第 560 题：和为 K 的子数组（中等）-一一网

摘要：前缀和与哈希表的问题一直很绕，感觉说不太清楚，最近会分享一些类似的问题，帮助大家巩固前缀和与哈希表的问题的解题思路。

未完成的点：

用具体的例子举例；

为什么不用「滑动窗口」，因为有负数。

题解 | 「力扣」第 560 题：和为 K 的子数组（中等）

给定一个整数数组和一个整数 $k$ ，你需要找到该数组中和为 $k$ 的连续的子数组的个数。

示例 1：

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
复制代码

示例 2：

Input: nums = [1,2,3], k = 3
Output: 2
复制代码

数据范围：

$1 \le nums.length \le 2 * 10^4$
$-1000 \le nums[i] \le 1000$
$-10^7 \le k \le 10^7$

方法一：暴力解法（超时）

枚举所有连续子数组，进而判断连续子数组的和是否等于 $k$

参考代码 1：

public class Solution {

    public int subarraySum(int[] nums, int k) {
        int len = nums.length;
        int count = 0;
        for (int left = 0; left < len; left++) {
            for (int right = left; right < len; right++) {

                int sum = 0;
                for (int i = left; i <= right; i++) {
                    sum += nums[i];
                }
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}
复制代码

时间复杂度： $O(N^3)$ ，这里 $N$ 是数组的长度。

方法二：通过「前缀和」计算区间和

构建前缀和数组，以快速计算区间和；
注意在计算区间和的时候，下标有偏移。

参考代码 3：

public class Solution {

    public int subarraySum(int[] nums, int k) {
        int len = nums.length;
        // 计算前缀和数组
        int[] preSum = new int[len + 1];
        preSum[0] = 0;
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }

        int count = 0;
        for (int left = 0; left < len; left++) {
            for (int right = left; right < len; right++) {
                // 区间和 [left..right]，注意下标偏移
                if (preSum[right + 1] - preSum[left] == k) {
                    count++;
                }
            }
        }
        return count;
    }
}
复制代码

时间复杂度： $O(N^2)$ ，这里 $N$ 是数组的长度。

即使计算了前缀和，枚举区间和也需要 $O(N^2)$ 的时间复杂度。优化的方法是：在遍历的过程中记住一些信息。

方法三：前缀和 + 哈希表

由于只关心次数，不关心具体的解，我们可以使用哈希表加速运算。由于保存了之前相同前缀和的个数，计算区间总数的时候不是一个一个地加，时间复杂度降到了 $O(N)$ 。

这个思路不是很容易想到，需要多做一些类似的问题慢慢培养感觉。类似的问题还有：

参考代码 4：

import java.util.HashMap;
import java.util.Map;

public class Solution {

    public int subarraySum(int[] nums, int k) {
        // key：前缀和，value：key 对应的前缀和的个数
        Map<Integer, Integer> preSumFreq = new HashMap<>();
        // 对于下标为 0 的元素，前缀和为 0，个数为 1
        preSumFreq.put(0, 1);

        int preSum = 0;
        int count = 0;
        for (int num : nums) {
            preSum += num;

            // 先获得前缀和为 preSum - k 的个数，加到计数变量里
            if (preSumFreq.containsKey(preSum - k)) {
                count += preSumFreq.get(preSum - k);
            }

            // 然后维护 preSumFreq 的定义
            preSumFreq.put(preSum, preSumFreq.getOrDefault(preSum, 0) + 1);
        }
        return count;
    }
}
复制代码