560. 和为 K 的子数组 (Subarray Sum Equals K)

难度： 🟡 中等

📖 题目描述

给你一个整数数组 $nums$ 和一个整数 $k$ ，请你统计并返回 该数组中和为 $k$ 的子数组的个数。

子数组 是数组中元素的连续非空序列。

📥 示例

示例 1：

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

输出： 2

解释： 符合条件的子数组为 [1, 1]（前两个）和 [1, 1]（后两个）。

示例 2：

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

输出： 2

解释： 符合条件的子数组为 [1, 2] 和 [3]。

📋 提示

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

💡 核心解法回顾（前缀和 + 哈希表）

基本原理： 子数组和 $\text{sum}(i, j) = \text{prefixSum}[j] - \text{prefixSum}[i-1]$ 。
等式转换： 我们要找的是 $\text{prefixSum}[j] - \text{prefixSum}[i-1] = k$ ，即 $\text{prefixSum}[i-1] = \text{prefixSum}[j] - k$ 。
优化技巧： 使用哈希表记录前缀和出现的次数，将 $O(n^2)$ 的搜索降低到 $O(n)$ 。

解决“和为 K 的子数组”这类问题，最直观的暴力解法是嵌套循环（ $O(n^2)$ ），但在数据量较大（ $2 \times 10^4$ ）且包含负数的情况下，最优雅且高效的方案是利用前缀和 (Prefix Sum) 结合 哈希表 (Hash Map)。

由于数组中存在负数，传统的“滑动窗口”法在这里行不通（因为窗口内数值的和不具有单调性）。

核心解题思路

1. 前缀和的物理意义

假设 $P[i]$ 是数组从开头到下标 $i$ 的元素之和。那么，任意一个连续子数组 $[j, i]$ 的和可以表示为：

$\text{Sum}(j, i) = P[i] - P[j-1]$

我们的目标是找到有多少组 $(j, i)$ 满足：

$P[i] - P[j-1] = k$

2. 等式变形

将上面的公式稍作变形：

$P[j-1] = P[i] - k$

这意味着：当我们遍历到下标 $i$ 时，如果在此之前（下标 $0$ 到 $i-1$ ）出现过前缀和等于 $P[i] - k$ 的情况，那么从那个位置到当前位置的子数组和就一定等于 $k$ 。

3. 哈希表的妙用

我们不需要真的去记录所有的 $P[j-1]$ ，只需要用一个哈希表来存储每个前缀和出现的次数。

Key: 前缀和的值。
Value: 该前缀和出现的频率。

特别注意： 在开始遍历前，需要先在哈希表中存入 {0: 1}。这代表前缀和为 0 已经出现过一次（用于处理从数组第一个元素开始就满足和为 $k$ 的情况）。

JavaScript 代码实现

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    // map 用于存储前缀和及其出现的次数
    const map = new Map();
    // 初始化：前缀和为 0 出现了 1 次
    map.set(0, 1);
    
    let count = 0;
    let currentSum = 0;
    
    for (const num of nums) {
        // 1. 累加当前元素，得到当前的前缀和
        currentSum += num;
        
        // 2. 检查 map 中是否存在 (currentSum - k)
        // 如果存在，说明找到了符合条件的子数组
        if (map.has(currentSum - k)) {
            count += map.get(currentSum - k);
        }
        
        // 3. 更新当前前缀和在 map 中的出现次数
        map.set(currentSum, (map.get(currentSum) || 0) + 1);
    }
    
    return count;
};

复杂度分析

时间复杂度： $O(n)$

我们只需要遍历一遍数组。哈希表的插入和查找操作在平均情况下都是 $O(1)$ 的。
空间复杂度： $O(n)$

在最坏情况下（所有前缀和都不相同），哈希表需要存储 $n$ 个不同的键值对。

举例演示

以 nums = [1, 2, 3], k = 3 为例：

初始化 map = {0: 1}, count = 0, currentSum = 0。
遍历 1: currentSum = 1。检查 1 - 3 = -2 不在 map 中。更新 map = {0:1, 1:1}。
遍历 2: currentSum = 3。检查 3 - 3 = 0 在 map 中，count += map.get(0) -> count = 1。更新 map = {0:1, 1:1, 3:1}。
遍历 3: currentSum = 6。检查 6 - 3 = 3 在 map 中，count += map.get(3) -> count = 2。更新 map = {0:1, 1:1, 3:1, 6:1}。
结果返回 2。

这种方法的精妙之处在于它将区间求和问题转化为了频率计数问题，从而绕过了 $O(n^2)$ 的暴力枚举。这种“一看就懂，一写就废”或者“过几天就忘”的情况非常普遍。这是因为前缀和+哈希表的解法虽然代码短，但它违背了我们直观的“切片式”思考逻辑。

为了让你彻底记住并理解，我们换一个视角，用**“修路”和“找标记”**的逻辑来重新解构它。

1. 建立直觉：路程与里程碑

想象你在一条公路上开车，路边每隔一段距离有一个里程碑。

前缀和（Prefix Sum）：就是你仪表盘上显示的总行程。
子数组（Subarray）：就是你从某一个里程碑 A 到 另一个里程碑 B 之间行驶的那段路。

如果你想找一段刚好 $k$ 公里长的路，你会怎么做？

你不需要每次停下来往回量。
你只需要看一眼现在的总里程 $S$ 。
然后问自己：“在之前路过的里程碑里，有没有哪个里程碑的记录恰好是 $S - k$ ？”
如果有，那么从那个里程碑到你现在位置的这段路，长度一定就是 $k$ 。

2. 为什么一定要用哈希表（Map）？

如果你每走一步，都要回头去翻所有的里程碑记录，那效率就是 $O(n^2)$ 。

哈希表在这里的作用是**“瞬间定位”**。

你把路过的每一个“总里程”都随手记在一个小本子（Map）上。
本子里记录的是：这个里程数出现了多少次。
当你到达新位置时，你不是在找 $k$ ，而是在找那个能凑出 $k$ 的“旧记录”（即 $currentSum - k$ ）。

3. 最容易忘的细节：为什么要初始化 `{0: 1}`？

这是很多人记不住的坑。

物理意义：在你还没起步（数组一个元素都没加）时，你的总行程就是 0。
逻辑意义：如果数组从第一个元素开始，加到某个位置正好等于 $k$ （比如 $nums=[3, 1], k=3$ ），此时 $currentSum = 3$ 。
计算 $currentSum - k = 3 - 3 = 0$ 。
如果你的 Map 里没有记录过 0，你就漏掉了这个从头开始的子数组。

所以，初始化 {0: 1} 是为了给“从头开始就满分”的情况一个机会。

4. 总结成一个“三步口诀”

如果你下次记不住代码，就回想这三步：

累加记录：一边走一边把路上的数加起来（currentSum）。
回头查账：看看 Map 里有没有我的“差值伙伴”（currentSum - k）。有几个，就加几个。
登记入库：把自己当前的这个总和也记到 Map 里，给后面的人当“伙伴”。

5. 什么时候该想到这个套路？

只要题目满足以下两个条件，脑子里就应该跳出这个方案：

关键词：连续子数组、求和、等于 $k$ 。
元素特征：数组里有负数（这意味着你不能用简单的滑动窗口，因为窗口里的和会忽大忽小，没有单调性）。