LeetCode Hot 100 里的 560 题“和为 K 的子数组”，我前前后后刷了三遍，每次都有新的理解。这道题在面试和算法学习中出现的频率极高，看起来只是“数一数有多少个连续子数组的和等于 k”，可真正把它讲透的人不多。很多解法上来就丢出前缀和加哈希表，却没人解释清楚为什么能这么想、为什么要先查询再更新、为什么不能用滑动窗口。这篇文章就是来补这份功课的，我会按我从暴力到最优解的真实思考路径展开，把每一步的推导、代码和踩坑都写清楚，适合刚接触前缀和的新手，也适合想把这题讲明白再去面试的老手。
1. 初见这道题：暴力解法到底卡在哪里
1.1 题目到底在问什么
先看题面。给定一个整数数组nums和一个整数k，需要返回该数组中“和为 k 的连续子数组”的个数。这里有几个词值得抠一下：
- 连续：子数组必须是数组中一段紧挨着的元素，不能跳着选。
- 子数组：区别于子序列，子数组强调连续，所以
[1,2]和2,3]是合法子数组，[1,3]不是。 - 个数：同一个元素可以出现在多个合法子数组里，位置不同就算不同答案。
举个例子，nums = [1, 1, 1]，k = 2，答案是 2。为什么是 2？因为第一个和第二个元素可以组成[1,1]，第二个和第三个元素也可以组成[1,1]，这两段虽然元素位置相邻但起点不同，都算作单独的子数组。
我刚开始刷这道题时，最容易被“连续”两个字带走，下意识想用双指针或者滑动窗口。因为很多“连续子数组”类问题都可以用滑动窗口优雅解决，比如“长度最小的子数组”那种。但 560 这道题有个隐藏陷阱：题目并没有说数组元素都是正数。只要数组里有负数，窗口的伸缩就失去了单调性，双指针的办法立刻失效。这一点后面我会专门展开讲。
1.2 先写一个能跑的版本
不管三七二十一，先把暴力解写出来，保证逻辑正确。最直接的想法是枚举所有可能的子数组起点i和终点j，累加区间内元素并判断是否等于k。
def subarraySum(nums, k): n = len(nums) ans = 0 for i in range(n): s = 0 for j in range(i, n): s += nums[j] if s == k: ans += 1 return ans这段代码我在本地跑了几个用例，逻辑正确性没问题。注意这里我用了一个小技巧：内层循环里s是逐步累加的，不需要每轮重新sum(nums[i:j+1])，这就能把时间复杂度控制在 O(n²) 而不是 O(n³)。如果谁真在循环里调sum，那复杂度直接爆炸，LeetCode 的测试用例会教做人。
但 O(n²) 依然是不可接受的。nums的长度上限是2 * 10^4，n²是4 * 10^8量级。Python 每秒大概能跑10^7到10^8次简单操作，这个规模随随便便超时。Java 和 C++ 会好一点，但同样非常吃力，而且这不是性能调优能解决的问题，算法层面就要换思路。
1.3 暴力解法里藏着什么重复劳动
写暴力解法不能写完就扔，要问自己一个问题：它慢在哪儿？
回头仔细看内层循环：当i固定时，我在不断计算nums[i] + ... + nums[j]。当i变到下一个位置，nums[i+1] + ... + nums[j]又是一遍完全独立的求和。这些区间和之间其实存在大量可以复用的关系。
假设我提前算好pre[i] = nums[0] + nums[1] + ... + nums[i-1]，那么任意子数组nums[j..i]的和就是pre[i+1] - pre[j]。这样一来，判断“子数组和是否等于 k”就变成了“两个前缀和的差是否等于 k”，完全不需要真的去加一段元素。这个观察是整道题从 O(n²) 降到 O(n) 的钥匙。
2. 从前缀和到哈希表：思考路径的完整推导
2.1 前缀和就是一张累计成绩单
前缀和的直觉特别像上学时考试的成绩累计表。假设你有三次考试分数分别是 80、90、95，那“到第二次为止的总分”是 170，“到第三次为止的总分”是 265，两次累计总分之差 265 - 170 = 95，恰好是第三次考试的分数。
数组也一样。定义preSum[i]表示从数组开头到下标i-1的所有元素之和，即前i个元素的总和。那么从下标j到下标i-1的连续子数组之和可以写成：
sum(nums[j..i-1]) = preSum[i] - preSum[j]这个公式是整个算法的心脏。它把一个“求一段连续区间和”的问题，变成了“两个前缀和相减”的问题。而这个减法恰好等于k，说明preSum[i] - preSum[j] = k，移项一下就是：
preSum[j] = preSum[i] - k也就是说，我们在遍历到位置i时，真正关心的是“前面已经出现过的前缀和里，有多少个等于preSum[i] - k”。只要数出这些个数，累加起来就是答案。
2.2 把问题改写成“两数之和”
如果你刷过 LeetCode 第一题“两数之和”，看到preSum[j] = preSum[i] - k一定会有似曾相识的感觉。两数之和是在数组里找两个数，让它们的和等于目标值；这里是在一堆历史前缀和里找一个值，让它等于当前前缀和减去k。本质上都是用一个哈希表把“查找”的代价从 O(n) 降到 O(1)。
我记得第一次推到这里时特别兴奋，因为感觉自己不是背答案，而是真的把知识串联起来了。后来的经验也印证了这一点：560 这道题放在 Hot 100 里，最大的学习价值不是让你记住哈希表的写法，而是帮你建立“遇到区间和问题先想前缀和，遇到查找问题先想哈希表”的敏感度。
2.3 为什么要边遍历边记录
理论上，我们可以先遍历一遍数组，把所有前缀和算出来存进一个列表，再遍历一遍列表做匹配。但这样有两个问题：
- 需要额外的数组保存全部前缀和，空间 O(n)。
- 第二遍遍历时，要能区分前缀和出现的先后顺序，避免把“未来的前缀和”算进“历史的匹配”里。
更聪明的做法是只遍历一遍数组，在遍历过程中维护“当前前缀和”。每走到一个位置，先查哈希表里有多少历史前缀和满足条件，再把当前前缀和放进哈希表。这样既不用保存整个前缀和数组，又能天然保证查询到的都是已经出现过的位置，不会出现“拿将来的前缀和匹配现在的自己”这种逻辑错误。
这种“边算边查边记”的套路，在后续很多题目里都会反复出现，比如“连续数组”“和可被 K 整除的子数组”。我建议直接把这一套思路当作模板刻在脑子里。
3. 哈希表 + 前缀和的完整实现
3.1 算法流程和那个关键的初始值
正式写代码前，先把流程理顺。我们需要一个变量cur记录当前位置的前缀和，一个哈希表map记录“每个前缀和值出现了多少次”。
遍历数组每个元素num：
cur += num，更新当前前缀和。- 查询
map中cur - k的个数，加到答案里。 - 把
cur自己也存进map，次数加一。
有一个细节必须敲黑板：初始化时，要让map[0] = 1。为什么？
因为前缀和为 0 的情况天然存在一个：一个元素都没选时，前缀和就是 0。这个空的前缀和对应的是“从数组开头到某个位置”的完整前缀。比如nums = [1, 2, 3]，k = 3，当遍历到下标 2（元素 3）时，cur等于 6，查询cur - k = 3，这个 3 在哪里？在遍历到下标 1 时记录过。所以答案是 1。可如果我想匹配的是下标 0 到下标 1 这段[1, 2]，那查询前缀和 0 的时机是在遍历到下标 1 时，cur - k = 0，此时如果没有map[0] = 1，这个答案就会被漏掉。
直观理解：map[0] = 1代表“在数组开始之前就已经存在一个和为 0 的前缀”，它让“从数组开头开始的子数组”也能被正确计数。漏掉这一行，你的代码会过不了[1, 2, 3], k = 3这类用例。
3.2 代码实现：Python、Java、C++ 三连
思路清楚了，代码只是翻译。
Python 版本：
def subarraySum(nums, k): from collections import defaultdict map = defaultdict(int) map[0] = 1 cur = 0 ans = 0 for num in nums: cur += num ans += map[cur - k] map[cur] += 1 return ansJava 版本：
public int subarraySum(int[] nums, int k) { Map<Integer, Integer> map = new HashMap<>(); map.put(0, 1); int cur = 0, ans = 0; for (int num : nums) { cur += num; ans += map.getOrDefault(cur - k, 0); map.put(cur, map.getOrDefault(cur, 0) + 1); } return ans; }C++ 版本：
int subarraySum(vector<int>& nums, int k) { unordered_map<int, int> map; map[0] = 1; int cur = 0, ans = 0; for (int num : nums) { cur += num; ans += map[cur - k]; map[cur]++; } return ans; }三个版本逻辑完全一致，就是哈希表的 API 不同。这里我用defaultdict而不是普通字典，就是不想写if cur - k in map这种判断，直接让缺失的键返回 0。代码能短一行是一行，刷题时尤其明显。
举个具体例子走一遍。nums = [1, 2, 3]，k = 3。
- 初始化：
map = {0: 1}，cur = 0，ans = 0。 - 遍历元素 1：
cur = 1，查询map[1 - 3] = map[-2] = 0，记录map[1] = 1。 - 遍历元素 2：
cur = 3，查询map[3 - 3] = map[0] = 1，ans = 1（匹配到子数组[1, 2]），记录map[3] = 1。 - 遍历元素 3：
cur = 6，查询map[6 - 3] = map[3] = 1，ans = 2（匹配到子数组[3]），记录map[6] = 1。
最终答案 2，和预期一致。整个过程每个元素只处理一次，哈希表的查询和插入都是 O(1)，总时间复杂度 O(n)，空间复杂度 O(n)。
3.3 先查询还是先更新：一步错，步步错
这是很多人第一次写这道题必踩的坑，也是面试官最爱追问的细节：遍历到位置i时，应该先查哈希表，还是先把当前前缀和放进哈希表？
答案是先查询，再更新。顺序反了会出大问题。
假设k = 0，数组是[0]。正确流程应该是：
cur = 0，先查询map[0] = 1，答案加 1，这对应空前缀匹配当前元素组成的子数组[0]。- 再更新，
map[0] = 2。
如果先把当前cur更新进哈希表再查询，会变成：
cur = 0，先更新map[0] = 2。- 再查询
map[0] = 2，答案加 2。
这就把同一个位置的前缀和算了两次，多出来的那一次对应的是一个“长度为 0 的虚拟子数组”，显然不合法。就算k不是 0，先更新也可能把“从当前位置开始的子数组”错误匹配成空区间，导致计数虚高。
我在 LeetCode 讨论区见过不少人贴出“看似简洁但顺序写反”的代码，在普通用例下跑不出来，但一遇到k = 0或者含0的数组就出错。所以不管多熟，我每次写完都会在脑子里走一个k = 0的用例，十几秒就能确认顺序没写反。
4. 常见问题与排查技巧实录
4.1 为什么不能用滑动窗口：负数这个搅局者
很多新手（包括当年的我）第一反应是用滑动窗口。在数组全为正数时，滑动窗口确实无懈可击：窗口和小于k就右扩，等于k就计数，大于k就左缩。原因在于全正数数组里，窗口和随着右边界扩大严格递增，左边界移动只会让和减少，这种单调性让滑动窗口能高效维护状态。
可一旦数组里出现负数，单调性立刻崩塌。右指针向右移动，窗口和可能变小；左指针向右移动，窗口和也可能变大。你没法判断下一步应该扩还是缩，滑动窗口的贪心逻辑不再成立。
举个例子。nums = [1, -1, 1, 1, 1]，k = 1。如果硬用滑动窗口，很容易漏掉[1, -1, 1]这种先增后减再增的子数组。所以记住一个判断标准：能用滑动窗口的连续子数组问题，前提通常是数组元素非负；一旦有负数，优先往前缀和上去想。
4.2k = 0和初始化map[0]究竟怎么配
k = 0是检验代码正确性的试金石。nums = [1, -1, 0]，k = 0，手动数一下应该有几个子数组？
[1, -1]：和为 0。[0]：和为 0。[1, -1, 0]：和为 0。
答案是 3。用哈希表解法跑一遍：
- 初始化
map = {0: 1}。 num = 1，cur = 1，查询map[1] = 0，记录map[1] = 1。num = -1，cur = 0，查询map[0] = 1，答案加 1（匹配[1, -1]），记录map[0] = 2。num = 0，cur = 0，查询map[0] = 2，答案加 2（匹配[0]和[1, -1, 0]），记录map[0] = 3。
最终答案 3，完全正确。你看第二次查询map[0] = 2时，两个计数分别对应两个不同的起点，这就是哈希表用“出现次数”而不是“是否存在”来存值的意义。很多类似题目只需要判断是否能组成目标值，存布尔值就行；这道题要返回个数，必须统计频次。
4.3 进阶变形：从计数到找具体子数组
如果面试官觉得这题你答得太顺，可能会加追问：能不能不只返回个数，而是返回所有满足条件的子数组？或者返回满足条件的最长子数组长度？
这些变形的核心思路还是前缀和，但哈希表里存的东西要升级。
- 要返回所有子数组，哈希表里得存“每个前缀和对应的所有下标集合”，一旦发现
cur - k存在，就遍历对应下标列表，构建子数组。复杂度会退化，但思路是通的。 - 要找和为
k的最长子数组长度，哈希表里存“每个前缀和第一次出现的位置（最左边）”，遍历时用当前位置减去最早位置，取最大值。核心逻辑是：前缀和相同的位置距离越远，中间这段子数组越“长”，也是最容易被人忽略的贪心点。 - 如果是二维矩阵，求子矩阵和等于
k的数量，思路变成“矩阵列前缀和 + 行区间遍历”，做法是固定上下边界，把每一列的和压缩成一维数组，再跑一遍这题的哈希表解法。
我在实际准备面试时，通常会把这三层变形一次讲给面试官听，一是展示自己对知识点有体系化理解，二是预防随机追问。别背答案，把“前缀和差值等于 k”这个本质抓住了，变形成什么样都能拆解。
4.4 一道题的时间复杂度怎么算才显专业
写代码只是完成了一半，能在面试里准确描述算法复杂度才算真正过关。
暴力解法的时间复杂度是 O(n²)，因为双重循环枚举所有起点终点。空间复杂度是 O(1)，只用了常数变量。
哈希表解法的时间复杂度是 O(n)，因为每个元素只遍历一次，哈希表查询和插入平均都是 O(1)。空间复杂度是 O(n)，因为最坏情况下每个前缀和都不同，哈希表里要存 n 个不同的键。
这里有一个值得提的点：Python 的dict和 Java 的HashMap平均是 O(1)，但在极端哈希冲突下可能退化为 O(n)。刷题和面试里，通常默认哈希表是 O(1)，不需要主动提冲突问题，除非面试官专门追问。如果你真想严谨，可以补一句“假设哈希分布均匀”。这种措辞会显得你既懂原理，又不钻牛角尖。
4.5 我复盘后总结的四个避坑清单
问题和技巧在前面分散讲了不少，这里集中整理一份我每次回顾时都会看的检查清单：
- 初始化别漏：
map[0] = 1这一行必须写，它代表数组开始前的空前缀，直接影响“整段子数组从开头开始”的情况。 - 先查询再更新：顺序搞反，遇到
k = 0时会把空子数组也算进去，计数虚高。 - 哈希表存频次而不是存在性：这道题返回个数，必须用
map[key] += 1累加次数，不是存一个true。 - 想清楚为什么不用滑动窗口：数组里有负数就放弃双指针，硬用滑动窗口只会陷入无止境的边界修补。
这份清单也是我每次面试前快速过一遍的“热身记忆”。
4.6 这题刷完，接下来推荐练什么
560 做完之后，强烈建议趁热打铁刷三道题巩固前缀和思维。第一道是 LeetCode 525“连续数组”，找含有相同数量 0 和 1 的最长连续子数组，核心是把 0 看成 -1，再做前缀和找相等。第二道是 974“和可被 K 整除的子数组”，找和为 K 的倍数，解法基于前缀和取模。第三道是 523“连续的子数组和”，判断是否存在连续子数组和是 k 的倍数且长度至少为 2，也是前缀和加哈希表的变体。
这三道题练完，你会发现前缀和加哈希表真的是一类题，不是孤立的单题。我当初连续刷完这几道后，最大的感受是：看到“子数组”“连续”“和”“整除”几个关键词，脑子里会自动浮现前缀和的框架，而不是傻傻从头暴力枚举。
还有一个小技巧：刷题时不要只看 LeetCode 的示例用例。示例太温和了，一定要自己补极端情况，比如空数组（虽然题目说了至少有 1 个元素，但面试时可以提）、全部为 0 的数组、只有一个元素的数组、全是负数的数组。这些边界用例能把代码里潜伏的 bug 逼出来。我自己写题解的惯例是：先过一遍正常用例，再过一遍k = 0，再过一遍所有元素相同，最后过一遍单元素数组。四类用例跑完，代码基本就稳了。
5. 写在最后的一点经验
如果你把这篇长文从头看到这里，说明你是真的想把这题吃透，而不仅仅是抄一份答案。按照我的经验，560 这道题至少值得刷三遍：第一遍看懂思路，第二遍不看答案默写，第三遍尝试给面试官讲清楚“为什么”。我自己就是刷到第三遍时，才把“为什么不能用滑动窗口”“为什么要初始化 map[0]”这些细节真正内化成肌肉记忆的。
刷题最忌讳的是背代码。代码会忘，但“边遍历边记录前缀和，用哈希表查历史”这个思路不会忘。我后来做很多事情也沿用了这个套路：先把问题转成可比较的差值，再建立索引去快速匹配，遇到数据量大到跑不动时，首先想的不是优化循环速度，而是减少重复计算。这种思维上的转移，才是刷算法题带给我最大的回报。
如果面试前只有五分钟回顾这道题，我会只看这句核心：子数组和等于 k，等价于两个前缀和之差等于 k；用哈希表记录前缀和出现的次数，边遍历边查询边更新。把这句能说透，560 这道题就算真正过关了。
