560. 和为 K 的子数组
难度：中等 | 主题：前缀和 + 哈希表
题目
给你一个整数数组 nums 和一个整数 k，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
示例
nums = [1,1,1], k = 2 → 输出 2
解释：[1,1]（前两个）和 [1,1]（后两个）
思路
先讲个故事：找零钱
你有一串售价标签，想找连续几件商品总价正好是 K 元。你从第一家店开始不停往购物车里加，每加一件就算一下当前总价。如果当前总价比目标多 K，你就回头看——之前有没有哪个时刻总价比现在少 K？有的话，那段时间的购物车加起来就是 K。
这就是前缀和的核心思想：总价是前缀和，回头看的是哈希表。
引导式推导：从双重循环到前缀和
暴力法：枚举每个起点和终点，求和。O(n²) 或 O(n³)。
关键洞察：子数组和 = 前缀和之差
子数组 [j..i] 的和 = prefix[i] - prefix[j-1]
要等于 k → prefix[j-1] = prefix[i] - k
所以遍历到 i 时，只要知道「之前出现过多少次 prefix = prefix[i] - k」，就找到了多少个以 i 结尾的、和为 k 的子数组。
graph LR A["遍历到 i"] --> B["当前前缀和 = prefix"] B --> C["目标前缀和 = prefix - k"] C --> D["查哈希表：出现过几次？"] D --> E["累加进 count"] E --> F["把当前 prefix 存入哈希表"]
为什么是计数，不是存下标？ 这题求的是子数组个数，不是最长长度。同一前缀和可能出现在多个位置，每个位置对应一个不同的子数组。所以哈希表存的是出现次数，不是下标。
为什么初始化 {0: 1}？ 因为空前缀（还没遍历时）的前缀和为 0。如果 prefix[i] == k，那从开头到 i 的子数组就满足条件，需要查 prefix - k = 0 在哈希表中出现过——1 次刚好覆盖这种情况。
重要对比：前缀和 vs 滑动窗口
| 场景 | 方法 | 空间 |
|---|---|---|
| 全是正数 | 滑动窗口 | O(1) |
| 有负数 | 前缀和 + 哈希 | O(n) |
有负数时，窗口的伸缩失去单调性，滑动窗口不适用。
代码
def subarraySum(self, nums, k):
# 哈希表：前缀和 → 出现次数
# 初始化 {0: 1} 覆盖从开头开始的子数组
seen = {0: 1}
prefix = 0 # 当前前缀和
count = 0 # 满足条件的子数组个数
for num in nums:
prefix += num # 更新前缀和
target = prefix - k # 要找的前缀和
if target in seen:
count += seen[target] # 之前出现过几次，就有几个子数组
seen[prefix] = seen.get(prefix, 0) + 1 # 记下当前前缀和
return count
复杂度
| 指标 | 值 | 解释 |
|---|---|---|
| 时间 | O(n) | 一次遍历，哈希操作 O(1) |
| 空间 | O(n) | 哈希表最多存 n 个不同前缀和 |
实战考量
频率分析
出现在：字节/美团/阿里高频题，约 40% 的同类题会考「前缀和」题型。这题是最佳入门，一定要会。
延伸思考
Q：为什么有负数就不能用滑动窗口？
A：滑动窗口依赖窗口和的单调性——和太大时收缩左边界，和太小时扩展右边界。有负数时，收缩左边界可能让和变大，扩展右边界可能让和变小，窗口失去了单调性。
Q：初始化 {0: 1} 为什么是 1 不是 0？
A：空前缀和为 0 出现了 1 次。当 prefix[i] == k 时，查 target = 0，seen[0] = 1 刚好 count 加 1。
Q：如果数组全是正数，最优解是什么？
A：滑动窗口，时间 O(n) 空间 O(1)。但通常期望你会两种——先讲滑动窗口（正数），再讲前缀和（通用）。
Q：如果要输出所有满足条件的子数组呢？
A：哈希表存下标列表，查到符合的前缀和时，回溯构造所有子数组。
Q：和 525连续数组 有什么区别？
A：这题求个数（哈希表存次数），525 求最长长度（哈希表存最早下标）。一个数数，一个测距。
易错点
-
初始化
{0: 1}不能漏 -
seen[prefix]加次数是seen.get(prefix, 0) + 1，不是直接赋值 1 -
count += seen[target]，不是count += 1（同一前缀和可能对应多个子数组） -
有负数时不能用滑动窗口
生活类比
找零钱 → 前缀和 → 哈希表
你站在收银机前，顾客不断往购物车里加商品。
每加一件你算一次总价，然后回头看：之前有没有总价比现在少正好 K 的时候？
有——那段时间买的东西就是 K 元。
把每次总价写在便利贴上贴墙上，下次回头看就快了。
哈希表就是那面墙。
相关题目
| 题目 | 关系 |
|---|---|
| 01两数之和 | 核心思想同源：都是「当前 - 目标」查哈希表 |
| 525连续数组 | 同前缀和题型，求最长 vs 求个数 |
| 128最长连续序列 | 哈希集优化，思路类似但不是前缀和 |
→ 返回题单：LeetCode学习路线图 > 一、数组与哈希（含双指针、矩阵）
速记卡（面试闪卡）
Q1：一句话讲清「560. 和为 K 的子数组」到底是什么？
A：统计数组中和为 k 的连续子数组的个数。
Q2：题目 —— 怎么理解？
A：像找连续几件商品总价正好 K 元：给定整数数组 nums 和整数 k，返回和为 k 的连续非空子数组个数。例 [1,1,1] k=2 → 输出 2（前两个和后两个各一段）。
Q3：思路 —— 怎么理解？
A：用前缀和查哈希表：子数组和 = 前缀和之差，要等于 k 即 prefix[j-1]=prefix[i]-k。遍历到 i 时查哈希表”之前出现过几次 prefix-k”，就是以此结尾的满足条件的段数。
Q4：代码 —— 怎么理解？
A：哈希表 seen 存”前缀和→出现次数”，初值 {0:1} 覆盖从开头开始的段；每步 prefix+=num，count+=seen.get(prefix-k,0)，再把 prefix 计数+1。一遍遍历 O(n) 搞定。
Q5：复杂度与实战考量 —— 怎么理解？
A：时间 O(n)、空间 O(n)。注意初始化 {0:1} 不能漏；有负数时滑动窗口失效（失去单调性）必须用前缀和；count += seen[target] 而非 +1（同一前缀和对应多段）。
Q6：核心速记主线有哪些？
-
核心：前缀和之差 = 子数组和
-
哈希存”前缀和→次数”，查 prefix-k
-
初值 {0:1} 覆盖开头段
-
有负数弃滑动窗口，用前缀和
口诀
A：和为 K 子数组，前缀之差来定位；
哈希记次查 target，几时出现几段对；
零次初值莫遗漏，负数窗口会失位；
一遍遍历 On 过，计数加次别加一。