和为 K 的子数组

更新: 7/5/2026 字数: 0 字 时长: 0 分钟

LeetCode 560. Subarray Sum Equals K

题目描述

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

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

示例：

输入：nums = [1,1,1], k = 2
输出：2
解释：子数组 [1,1]（下标 0~1）和 [1,1]（下标 1~2）的和都为 2。

输入：nums = [1,2,3], k = 3
输出：2
解释：[1,2] 和 [3] 的和都为 3。

约束：，，。

注意

数组里可能有负数，所以「滑动窗口」在这里不适用（窗口和不单调，缩小窗口不一定让和变小）。这是本题的第一个关键判断。

思路拆解：从暴力到最优

想法一：双重循环枚举所有子数组（暴力解法）

最直接的想法：枚举所有子数组的「起点 i、终点 j」，累加区间和，判断是否等于 k。

点击展开暴力解法

function subarraySum(nums, k) {
  let count = 0;
  for (let i = 0; i < nums.length; i++) {
    let sum = 0;
    for (let j = i; j < nums.length; j++) {
      sum += nums[j];        // 累加 [i..j] 的和
      if (sum === k) count++;
    }
  }
  return count;
}

• 时间：，两层循环。（固定起点、向右扩展终点，已经用「边扩展边累加」省掉了第三层求和。）
• 空间：。

时 约 4 亿次操作，勉强踩线甚至超时。我们需要 的解法。

想法二：前缀和 + 哈希表（最优解）

先引入前缀和：设 preSum[i] 表示 nums[0..i-1] 的累加和。那么任意子数组 nums[i..j] 的和可以用两个前缀和相减得到：

我们要找「和为 k 的子数组」，即找满足下式的配对：

核心思路

边遍历边维护「当前前缀和 sum」，用哈希表记录「每个前缀和出现过多少次」。

当扫描到某个位置、当前前缀和为 sum 时，我们想知道：前面有多少个位置的前缀和等于 sum - k？每一个这样的位置，都对应一个「以当前位置结尾、和为 k」的子数组。

于是算法变成：

1. 哈希表 map 存「前缀和 → 出现次数」，初始化 map[0] = 1（表示「空前缀」，和为 0 出现过一次）。
2. 遍历数组，累加 sum。
3. 查 map 里 sum - k 出现了几次，累加进答案 count。
4. 再把当前 sum 记入 map（次数 +1）。

为什么要 map[0] = 1？ 它表示「什么都不加时前缀和为 0」。这样当某个前缀和本身正好等于 k 时（即从头到当前整段和为 k），sum - k = 0 能在表里查到这一次，把「从下标 0 开始」的子数组正确计入。

动态演示

下面的动画完整演示了对 nums = [1,2,3], k = 3 的前缀和 + 哈希表全过程——看指针如何逐个扫描、sum 如何累加、每一步如何去哈希表里查 sum - k 并更新答案：

步骤 1 / 13初始化

目标 k = 3当前 sum = 0答案 count = 0

01

12

23

哈希表（前缀和 → 出现次数）

0→1

初始化：哈希表放入 {0: 1}，表示「空前缀」的和 0 已出现 1 次。sum=0，count=0。

完整代码（JavaScript）

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
function subarraySum(nums, k) {
  const map = new Map();
  map.set(0, 1);        // 关键：前缀和为 0 出现 1 次（空前缀）

  let sum = 0;          // 当前前缀和
  let count = 0;        // 答案
  for (const x of nums) {
    sum += x;                          // 1) 累加当前前缀和
    if (map.has(sum - k)) {            // 2) 查 sum-k 出现过几次
      count += map.get(sum - k);       //    每一次对应一个合法子数组
    }
    map.set(sum, (map.get(sum) || 0) + 1); // 3) 记录当前前缀和
  }
  return count;
}

顺序很重要

必须先查 sum - k，再把当前 sum 记入哈希表。如果顺序反了，当 k = 0 时会把当前位置自己也算进去，导致多计。这是本题最隐蔽的坑。

复杂度分析

设数组长度为 。

解法	时间复杂度	空间复杂度	说明
暴力枚举			双重循环， 大会超时
前缀和 + 哈希表			一次遍历，哈希表最多存 个前缀和，最优

为什么最优解是 ？ 只遍历数组一遍，每个元素做常数次哈希表查询与插入（平均 ），所以总时间线性。代价是哈希表最多存 个不同前缀和，空间 ——这是典型的「用空间换时间」。

边界与易错点

易错点

1. 必须初始化 map[0] = 1。否则「从下标 0 开始、整段和恰为 k」的子数组会漏计。这是最常见的错误。

2. 先查询，后插入。顺序不能颠倒，否则 k = 0 时会把当前元素自身错误地算作一个和为 0 的子数组。

3. 有负数，不能用滑动窗口。因为负数会让前缀和非单调，窗口收缩无法保证和的变化方向，滑窗的正确性前提被破坏。只能用前缀和 + 哈希表。

4. 统计的是「个数」不是「是否存在」。同一个前缀和可能出现多次，所以哈希表存的是出现次数，累加时要 count += map.get(sum - k)，而不是简单 count++。

5. 前缀和可能很大 / 为负。用哈希表（Map）而非数组做索引，天然支持负数和大数值作为键，无需担心越界。

6. 子数组要求连续且非空。前缀和相减恰好对应连续区间；map[0]=1 保证的是长度 ≥ 1 的子数组，不会计入空子数组。

简易解题思路（记忆口诀）

「前缀和边走边攒，哈希表记它几遍；先查 sum 减 k 见没见，见几次答案加几遍；查完再把自己填，别忘 0 号先占一间。」

拆开记：

口诀	对应操作
前缀和边走边攒	sum += x，维护当前前缀和
哈希表记它几遍	map 存「前缀和 → 出现次数」
先查 sum 减 k	count += map.get(sum - k)
查完再把自己填	map.set(sum, cnt+1)，顺序不能反
0 号先占一间	初始化 map.set(0, 1)

一句话记住本质：「区间和 = 两前缀和之差」，所以边走边攒前缀和，每到一处就问哈希表「有没有一个更早的前缀和，让这段差正好等于 k」——有几个就加几个。