560. 和为 K 的子数组
560. 和为 K 的子数组
题目链接（中等）
题目描述
给你一个整数数组 nums 和一个整数 k，请你统计并返回该数组中和为 k 的子数组的个数。
子数组是数组中元素的连续非空序列。
数据范围：
1 <= nums.length <= 2 * 10^4-1000 <= nums[i] <= 1000-10^7 <= k <= 10^7
示例
示例 1：
输入： nums = [1,1,1], k = 2
输出： 2
示例 2：
输入： nums = [1,2,3], k = 3
输出： 2
核心思路
朴素做法：枚举子数组的开头和结尾，判断和是否为 k。
优化思路：用前缀和 + 哈希表。
前缀和定义：pre[i] = nums[0] + nums[1] + ... + nums[i]。
关键观察：子数组 [j..i] 的和为 k，等价于：
移项得：
也就是说：以 i 结尾、和为 k 的子数组个数，等于「值为 pre[i] - k 的前缀和」出现的次数。
用哈希表记录「每个前缀和出现的次数」，边遍历边查询，就能做到 $O(1)$ 判断。
注意：前缀和可以为负数，所以不能用双指针 / 滑动窗口，必须用哈希表。
方法一：枚举（$O(n^2)$）
思路及解法
固定子数组的结尾 end，向前枚举开头 start，边累加边判断。
因为是从 end 向前累加，每次加上 nums[start] 就能在 $O(1)$ 内得到 [start..end] 的和。
代码
class Solution:
def subarraySum(self, nums: list[int], k: int) -> int:
n = len(nums)
count = 0
for end in range(n):
total = 0
for start in range(end, -1, -1):
total += nums[start]
if total == k:
count += 1
return count复杂度分析
- 时间复杂度：$O(n^2)$，枚举 $O(n)$ 个结尾，每个结尾向前枚举 $O(n)$ 个开头。
- 空间复杂度：$O(1)$。
方法二：前缀和 + 哈希表（推荐）
思路及解法
核心公式：子数组 [j..i] 的和为 k ⟺ pre[j-1] = pre[i] - k。
流程：
- 用哈希表
mp记录「每个前缀和出现的次数」； - 初始化
mp[0] = 1，表示前缀和为 0 出现过 1 次（处理「子数组从下标 0 开始」的情况）； - 遍历
nums，维护变量pre表示当前前缀和：pre += nums[i]；- 查询
mp[pre - k]，把它的值累加到答案； - 把当前
pre加入哈希表：mp[pre] += 1；
- 返回累加的答案。
为什么初始化 mp[0] = 1？
- 若存在
pre[i] == k，说明nums[0..i]的和为k； - 这个子数组的「前缀和起点」是
pre[-1] = 0； - 所以需要
mp[0] = 1，让查询mp[pre - k] = mp[0]时能统计到这一种情况。
为什么边遍历边查询，不会重复？
因为我们先查询后更新：查询时哈希表里存的都是 pre[j]（j < i）的次数，不会把当前 pre[i] 也算进去。
例子：nums = [1,1,1]，k = 2
| 步骤 | i |
nums[i] |
pre |
mp 更新前 |
mp[pre-k] |
count |
mp 更新后 |
|---|---|---|---|---|---|---|---|
| 初始 | — | — | 0 | {0: 1} |
— | 0 | {0: 1} |
| 1 | 0 | 1 | 1 | {0: 1} |
mp[-1] = 0 |
0 | {0: 1, 1: 1} |
| 2 | 1 | 1 | 2 | {0: 1, 1: 1} |
mp[0] = 1 |
1 | {0: 1, 1: 1, 2: 1} |
| 3 | 2 | 1 | 3 | {0: 1, 1: 1, 2: 1} |
mp[1] = 1 |
2 | {0: 1, 1: 1, 2: 1, 3: 1} |
最终 count = 2，正确。
代码
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
prefix = defaultdict(int)
prefix[0] = 1
cur = 0
ans = 0
for num in nums:
cur += num
ans += prefix[cur - k]
prefix[cur] += 1
return ans复杂度分析
- 时间复杂度：$O(n)$，遍历数组一次，哈希表操作 $O(1)$。
- 空间复杂度：$O(n)$，哈希表最坏存储 $n$ 个不同的前缀和。
两种方法对比
| 方法 | 时间 | 空间 | 特点 |
|---|---|---|---|
| 枚举 | $O(n^2)$ | $O(1)$ | 思路最直观，数据小时可用 |
| 前缀和 + 哈希 | $O(n)$ | $O(n)$ | 效率最优，面试首选 |
推荐：
- 面试开场：先讲枚举，思路简单；
- 追问优化：再讲前缀和 + 哈希表，展示对「子数组和 → 前缀和之差」的转化。
关键细节
1. 为什么不能用滑动窗口
滑动窗口要求「窗口和随窗口扩展单调变化」。但本题数组元素可能为负数，窗口和不是单调的，无法用双指针。
举例：nums = [-1, -1, 1]，k = 1。窗口和会忽大忽小，双指针失效。
2. 前缀和可以为负数
因为 nums[i] 可以是负数，所以 pre 可以为负，哈希表的键可以是任意整数。
3. 为什么要「先查询后更新」
如果先更新再查询：
- 当
nums[i] = 0、k = 0时，会错误地把当前pre也算进去； - 实际上当前子数组「自己」不算，需要的是之前出现过的前缀和。
先查询后更新保证查询时只统计 j < i 的前缀和。
4. mp[0] = 1 的作用
处理「子数组从下标 0 开始」的情况。比如 nums = [3]，k = 3：
- 遍历到
3时，pre = 3，pre - k = 0； - 若
mp[0] = 1，则count += 1，正确统计； - 若没有
mp[0] = 1，则漏掉答案。
5. 与 LC 437（路径总和 III）的关系
两题的思路完全一致：
- LC 560：数组上「子数组和为
k」的数量； - LC 437：树上「路径和为
targetSum」的数量。
区别在于 LC 437 是树形结构，需要在 DFS 中维护前缀和并回溯。两题可以一起做，加深理解。
6. 哈希表 vs 数组
本题前缀和范围很大（可为负、可达 $10^7$），不能用数组当哈希表，必须用字典。
总结
- 核心公式：
pre[j-1] = pre[i] - k； - 哈希表：记录「每个前缀和出现的次数」；
- 初始化：
mp[0] = 1，处理「从下标 0 开始的子数组」； - 顺序：先查询
mp[pre - k]，再更新mp[pre] += 1； - 时间：$O(n)$；空间：$O(n)$；
- 易错点：
- 不能用滑动窗口（元素可能为负）；
- 必须先查询后更新，避免
0的干扰； mp[0] = 1不能少。
相关题目
- LC 437. 路径总和 III（树上版本的前缀和）
- LC 1. 两数之和（哈希表的经典应用）
- LC 1248. 统计「优美子数组」（哈希表 + 前缀和变形）
- LC 974. 和可被 K 整除的子数组（前缀和取模）
- LC 523. 连续的子数组和（前缀和取模 + 哈希）