刷力扣刷到 560 这道题的时候我第一反应是这题看起来挺简单——统计和为 k 的子数组个数暴力枚举起点和终点不就行了但一看数据范围nums.length最大能到 2 * 10^4O(n^2) 的暴力解法在最后一组数据上是肯定过不去的。于是“前缀和 哈希表”这个刷题圈里的高频组合就登场了。这道题在力扣热题 100 里占着一个位置也频繁出现在各家公司的面试题中。它表面上考的是数组遍历实际上考的是你能不能把“子数组求和”转化为“两个前缀和的差值”再用哈希表把查找过程从 O(n) 压到 O(1)。这个套路一旦理解了能解的不只是这一道题后面我列的一串同类题全都能顺手拿下。这篇文章我会从暴力解法讲起一步步推到前缀和再讲到哈希表优化把每一步的推导逻辑说清楚然后给 C、Java、Python 三种语言的完整实现和逐行解读。最后把我自己刷这道题踩过的一些坑整理成问题排查表再补充几个用同样套路能解的扩展题。1. 题目到底在考什么1.1 审题比写代码重要先说题目本身给你一个整数数组nums和一个整数k统计并返回该数组中和为k的连续子数组的个数。我见过不少同学第一次做这道题时翻车原因不是不会写代码而是没注意两个关键词。第一个关键词是“连续”。子数组必须是数组中一段连续的元素[1, 2, 3]里[1, 3]不是子数组因为跳过了2。这个看似废话但很多人用回溯或子集枚举去解就是把问题理解偏了。第二个关键词是“个数”。题目只要数量不要具体下标也不要去重——如果两个不同的起点和终点组合成相同的子数组值它们算两个不同的子数组。比如nums [0, 0]k 0那答案应该是 3因为[0]第一个、[0]第二个、[0, 0]都是符合条件的连续子数组虽然它们的元素值一样但起点终点不同。题目给的约束条件也值得看一眼数组长度最大 2 万nums[i]和k的取值范围里是有负数的。有负数这件事直接决定了你后面能不能用滑动窗口这一类解法我后面会在问题排查部分重点展开。1.2 暴力解法的演进先别急着背最优解我习惯在讲任何数组题时都从暴力解法开始因为暴力解法能帮你确认自己对题意的理解是对的。最直白的写法是三层循环枚举起点i枚举终点j然后从i到j累加求和判断是否等于k。这个写法的时间复杂度是 O(n^3)2 万的数据量下是绝对跑不完的但在本地用几个小样例验证思路没问题。稍微优化一下两层循环就够了枚举起点i然后从i开始往后逐步累加每加一个元素就判断当前累加和是不是等于k。这个做法的时间复杂度是 O(n^2)2 万的数据量下依然会超时但代码写出来只有几行很容易验证出自己对题意的理解。class Solution: def subarraySum(self, nums, k): n len(nums) count 0 for i in range(n): s 0 for j in range(i, n): s nums[j] if s k: count 1 return count这个暴力版本在某些小数据集上能过但它最大的问题在于每次枚举到一个新的终点我们都要从起点重新累加前面的计算结果完全浪费了。于是就有了前缀和这个优化思路——把“多次重复计算区间和”变成“一次预处理之后每次计算都是 O(1) 的减法”。2. 前缀和把子数组求和变成减法2.1 前缀和的直觉前缀和的定义非常简单prefix[i]表示原数组前i个元素的和。注意我这里是“前 i 个元素”所以prefix[0] 0prefix[1] nums[0]prefix[2] nums[0] nums[1]以此类推。为什么前缀和能把区间求和变成减法因为nums[j]到nums[i]这段连续元素的和等于prefix[i1] - prefix[j]。左边是前i1个元素的总和右边是前j个元素的总和两者一减中间nums[j]到nums[i]这一段就被单独拎出来了。这个思想特别像你在记录账本如果想知道 3 月到 5 月一共花了多少钱不需要把这三个月的每一笔都翻出来重新加一遍只需要用“截至 5 月的总花销”减去“截至 2 月的总花销”就行。前缀和干的正是这件事。有了前缀和数组我们就可以枚举起点了对每个终点i遍历所有可能的起点j用prefix[i1] - prefix[j]判断是否等于k。这个做法的时间复杂度仍然是 O(n^2)但相比暴力解法已经少了一层累加循环因为区间和不需要重复算了。话虽如此O(n^2) 在 2 万的数据量下依然不够。2.2 从 O(n^2) 到 O(n) 的关键推导把上一节的等式写下来prefix[i1] - prefix[j] k。这个式子可以变形。prefix[j] prefix[i1] - k。这个变形式就是整道题从 O(n^2) 到 O(n) 的钥匙。我们可以换个角度看当我们固定终点i时不需要去遍历所有起点j只需要知道“在此之前有多少个前缀和的值等于prefix[i1] - k”。因为每一个等于prefix[i1] - k的前缀和prefix[j]都对应着一个起点j而prefix[i1] - prefix[j] k意味着从j到i的这一段连续子数组和正好是k。所以问题就变成了一边遍历数组、一边记录已经出现过的前缀和每到一个新位置查一下“目标前缀和”出现过多少次。这个“记录出现次数 快速查询”的需求就是哈希表的用武之地。3. 哈希表优化全场最关键的一步3.1 哈希表里到底存什么哈希表的 key 是前缀和的值value 是这个前缀和值出现的次数。为什么要存次数因为相同的前缀和值可能出现多次每出现一次就意味着多了一个可能的起点。举个例子你就明白了。nums [1, -1, 1, -1]前缀和序列是0, 1, 0, 1, 0。前缀和 0 出现了三次分别对应下标0, 2, 4这里指 prefix 数组的下标。这三次出现就是三个不同的起点所以在哈希表里map[0] 3。当我们遍历到某个终点发现目标值是 0那从哈希表里拿到的3就表示有 3 个起点可以匹配也就是有 3 个符合条件的子数组。换句话说哈希表的 value 不是某个下标而是可选起点的数量这正好和题目要求的“个数”对应上了。还有一点要注意哈希表里存的前缀和是当前位置之前已经出现过的前缀和不包括当前这次计算出来的前缀和。这个先后顺序对k 0的情况特别敏感具体原因我在第 5 节用反例说明。3.2 为什么必须先查后存遍历数组时顺序一定是先计算当前前缀和查出目标值出现次数并累加到答案然后把当前前缀和存进哈希表。如果反过来先把当前前缀和存进去再查询会出大问题。考虑k 0的情况当前前缀和就是目标值如果先存再查当前前缀和会和“自己”匹配把一条根本不存在的子数组也算进去。好比你查自己是不是自己的下一任这种循环引用必然多算。我先给出标准顺序后面在第 5 节用完整反例算给你看先存后查到底会多出多少错误计数。3.3 初始值 (0, 1) 的含义哈希表在遍历开始前需要预置一个初始值map[0] 1。这个初始值非常容易被新手忽略也特别容易在面试时被追问。它的含义是在数组开始之前存在一个“空前缀”它的和是 0出现次数是 1。为什么要预置它因为如果prefix[i1] - k 0说明从nums[0]到nums[i]的整段子数组的和正好等于k。如果没有这个预置的空前缀整段子数组的情况就会被漏掉。打个比方你在统计从起点到当前点的所有路径每条路径都对应一个起点。你不可能凭空找到“从数组起点之前开始的路径”但整段数组从 0 开始所以必须人为加一个起点 0。少了这一行代码在碰到nums本身就是答案时全军覆没。4. 完整代码与逐行解读4.1 C 实现class Solution { public: int subarraySum(vectorint nums, int k) { unordered_mapint, int mp; mp[0] 1; // 空前缀 int prefix 0; int count 0; for (int num : nums) { prefix num; int target prefix - k; if (mp.count(target)) { count mp[target]; } mp[prefix]; } return count; } };C 里我用了unordered_map而不是map原因是unordered_map底层是哈希表查找和插入的平均时间复杂度都是 O(1)而map底层是红黑树操作复杂度是 O(log n)。这道题要频繁查询哈希表是最合适的选择。注意我在查询时用mp.count(target)判断是否存在这样能避免直接用mp[target]带来的副作用——operator[]在 key 不存在时会把 key 插入且 value 初始化为 0。如果每种 key 都被意外插入哈希表的空间开销会增加更严重的是它会产生“查询污染”让你误以为某个前缀和出现过。4.2 Java 实现class Solution { public int subarraySum(int[] nums, int k) { MapInteger, Integer map new HashMap(); map.put(0, 1); int prefix 0; int count 0; for (int num : nums) { prefix num; int target prefix - k; count map.getOrDefault(target, 0); map.put(prefix, map.getOrDefault(prefix, 0) 1); } return count; } }Java 实现里我用getOrDefault来处理目标值不存在的情况避免先get再判断null的繁琐写法。每次更新哈希表时也是用getOrDefault(prefix, 0) 1来累加计数这比先判断containsKey再取值要简洁不少。Java 的HashMap同样允许null值但这里我们对 key 的约束是前缀和不可能是 null所以不用额外处理。4.3 Python 实现class Solution: def subarraySum(self, nums: List[int], k: int) - int: # 哈希表记录前缀和出现的次数 cnt {0: 1} prefix 0 ans 0 for num in nums: prefix num target prefix - k ans cnt.get(target, 0) cnt[prefix] cnt.get(prefix, 0) 1 return ansPython 在力扣上用List[int]需要从typing导入但力扣的评测环境里已经默认处理了所以提交时不用写from typing import List。如果你在本地跑记得补上导入。我个人最喜欢 Python 写这类题因为dict.get(key, default)把查询和缺省值处理合在了一行整个函数缩进完只有 9 行。但要注意Python 的 dict 虽然快常数开销比 C 的unordered_map大好在 2 万的数据量下毫无压力。4.4 一个完整例子的手工走查光看代码还是不够直观我用手工走查的方式带你把流程跑一遍。用nums [1, 2, 3, -1, 1]k 3。初始化cnt {0: 1}prefix 0ans 0。第一步遍历到1。prefix 1target 1 - 3 -2查cnt[-2]不存在ans不变然后cnt[1] 1。第二步遍历到2。prefix 3target 3 - 3 0查cnt[0] 1说明以当前位置结尾、和为 3 的子数组有 1 个ans 1。这个 1 对应的是谁就是空前缀到当前终点也就是子数组[1, 2]。然后cnt[3] 1。第三步遍历到3。prefix 6target 6 - 3 3查cnt[3] 1ans 2。这个 1 对应子数组[3]。然后cnt[6] 1。第四步遍历到-1。prefix 5target 5 - 3 2查cnt[2]不存在ans不变。然后cnt[5] 1。第五步遍历到1。prefix 6target 6 - 3 3查cnt[3] 1ans 3。这个 1 对应的是谁前缀和为 3 的点出现在下标 2也就是 prefix[2] 3从下标 2 到当前位置 5 对应的子数组是[3, -1, 1]和为 3。最终ans 3。验证一下[1, 2]、[3]、[3, -1, 1]正好 3 个。注意第五步特别有意思我们并没有真的去遍历起点但通过哈希表找到了“哪个前缀和能满足条件”一次查找就确定了所有匹配的起点。这就是哈希表把 O(n) 起点枚举压缩成 O(1) 查询的核心表现。5. 常见问题与排查技巧5.1 为什么不能用双指针滑动窗口很多同学一看到“连续子数组求和”就想用双指针尤其是数组里全是正数的时候双指针加滑动窗口确实能把复杂度降到 O(n)。但一旦数组里有负数双指针就失效了。原因很简单滑动窗口依赖窗口和的单调性。当窗口内和大于k时右移左指针可以缩小窗口从而降低和但当数组里混入负数时右移左指针不一定能让总和变小——你丢掉一个较大的正数同时窗口里可能还留着几个绝对值巨大的负数。单调性被破坏双指针的移动策略就不成立了。nums [1, -1, 1, -1]这种数据双指针完全打不出正确结果。所以看到题目里有“负数”这个条件就要第一时间告诉自己滑动窗口这条路走不通考虑前缀和。5.2 为什么有负数时不能提前 break暴力解法里如果数组全为正数累加和一旦超过k后面再加只会更大可以提前跳出循环。这是一个常见剪枝思路。但这道题有负数累加和超过k之后加一个-100又变回k了。所以千万不能为了“优化”加if (sum k) break这类逻辑加了就漏解。我见过不少同学在暴力解法基础上试图剪枝结果样例一换就错。正确做法是放弃剪枝思路直接用前缀和 哈希表把复杂度做到 O(n)这比任何剪枝都有效。5.3 哈希表更新顺序引发的大坑再来验证一下“先查后存”的必要性。用nums [1, -1, 0]k 0正确答案是 3[1, -1]、[0]、[1, -1, 0]。如果错误地先存再查初始化cnt {0: 1}prefix 0ans 0。遍历1prefix 1先存cnt[1] 1再查target 1 - 0 1cnt[1] 1ans 1。但这里[1]并不等于 0错误计数 1。遍历-1prefix 0先存cnt[0] 2再查target 0cnt[0] 2ans 3。遍历0prefix 0先存cnt[0] 3再查target 0cnt[0] 3ans 6。最终答案是 6正确是 3多了整整一倍。所以查和存的顺序绝对不能换。这也解释了我在 3.2 里埋下的伏笔k 0时当前前缀和会和自己匹配先存后查必然出问题。5.4 溢出风险和边界 casenums[i]的范围是[-1000, 1000]数组长度最大 2 万理论上前缀和的范围在[-2*10^7, 2*10^7]之间int在 C 里通常够用。但很多同学喜欢在本地跑更长、更大的数据做压力测试这时候int就可能不够了。我的习惯是直接用long long存前缀和反正不损失性能还能省掉一类溢出隐患。边界 case 也要注意数组只有一个元素时比如nums [1]k 0答案是 0因为没有任何子数组和为 0。nums [1]k 1答案是 1。空数组的情况力扣约定不会出现但本地写测试用例时可以考虑一下确保哈希表初始值逻辑在长度 1 时也正确。6. 这个套路能解决的所有题目6.1 从一维到二维的扩展前缀和 哈希表不只解决 560它是处理“找满足某些条件的连续区间”这类问题的一整套方法论。我列几个高频同类题你可以拿同一个套路去解。974. 和可被 K 整除的子数组把前缀和对 K 取模哈希表记录模值出现的次数。注意取模结果需要调整为非负数用(prefix % K K) % K否则负数取模会带来各种边界问题。523. 连续的子数组和同样用前缀和对 K 取模但要求子数组长度至少为 2所以不能只记录次数而是要记录某个余数最早出现的下标每次查询时检查当前下标和最早下标的距离是否大于等于 2。1371. 每个元音包含偶数次的最长子字符串这个更进阶一点把元音字母的奇偶性压缩成状态配合前缀异或或状态 diff本质上还是“记录状态第一次出现的位置”。它表面上和“和为 k”无关但数据结构和使用方式如出一辙。1074. 元素和为目标值的子矩阵数量二维版本。先枚举上下边界把每一列的和压缩成一维数组然后对压缩后的数组跑 560 的套路。复杂度从一维的 O(n) 变成 O(m^2 * n)m 是行数但整体思路完全没变。刷完 560 之后我建议你按这个列表顺序做一遍。你会发现 560 是地基974、523 是在地基上改了取模和记录方式1371 是把状态压缩进 key1074 是把维度升到二维。一通百通。6.2 前缀和 哈希表解题模板最后给你一个可复用的模板很多题都能在它基础上微调def subarray_sum_template(nums, k): cnt {0: 1} # 初始空前缀按题目需要调整 value 的含义 prefix 0 ans 0 for x in nums: prefix x target prefix - k # 变式改成 (prefix % k) 等 ans cnt.get(target, 0) cnt[prefix] cnt.get(prefix, 0) 1 # 变式改成记录最早下标 return ans模板里的两处关键替换就是题目的变体入口你把target的计算方式换成题目要求的目标值把cnt的 value 从次数换成题目需要的信息就得到一个新题的解。我刷题这几年最深的体会是与其背几百道题的题解不如把这种“一套思路解一串题”的模板吃透。560 就是最好的切入点。拿到手先写暴力确认题意再用前缀和推导目标等式最后用哈希表压缩复杂度这个流程本身就是一套通用的解题方法论。以后看到“连续子数组 某种和/余数/状态条件”的题直接往这个框架里套效率会高很多。