LeetCode Hot 100 里的第560题“和为K的子数组”是我刷题过程中印象很深的一道题。题目本身只有一句话给定一个整数数组和一个整数K统计数组中有多少个连续子数组的和等于K。读完感觉很简单但真动笔写很多人会发现自己要么写出O(n³)的暴力循环要么在负数和零面前栽跟头。这道题真正想考察的不是你会不会写循环而是你对“前缀和 哈希表”这套组合技有没有吃透。这道题建议所有准备算法面试的朋友都花时间认真拆一遍。它表面是计数题实际上涉及几个很核心的算法思维暴力枚举怎么一步步优化、什么时候不能用滑动窗口、哈希表里存什么才能把时间复杂度从O(n²)降到O(n)。如果你能把这道题的来龙去脉讲清楚面试里遇到类似“连续子数组 条件计数”的题基本都能顺手解掉。1. 先搞清楚题目在问什么1.1 一个看似简单的统计问题题目给的数组是整数数组注意是“整数”不是“正整数”。这意味着数组里可能包含负数、零也可以全是一样的数字。要求统计的是连续子数组所谓连续子数组就是原数组中连续的一段比如nums[2]到nums[5]这样夹出来的一块。每个子数组可以只有一个元素也可以是整个数组甚至数组里每个单独的元素只要等于K都算一个满足条件的子数组。举个例子数组[1, 1, 1]K2答案是2。哪两个呢第一个子数组是[1, 1]下标0到1第二个是[1, 1]下标1到2。这两个子数组虽然长得一样但因为位置不同是两条不同的子数组所以计数2。这一点很重要暴力和前缀和方案都要确保把这种“位置不同就算不同子数组”的情况算进去。1.2 连续子数组的两个隐蔽陷阱第一个陷阱是“连续”两个字。很多新手一开始会去想组合数学试图用排列组合的方式算出多少个和等于K然后就被绕晕了。但其实连续子数组不关心元素怎么排它只关心原数组中一段一段的窗口每段就是一个连续区间所以问题的本质是有多少个区间[i, j]满足下标从 i 到 j 的所有元素和正好等于K。第二个陷阱是数组里有负数。负数会让“当前累加和”变得不单调。你从前往后累加可能加了几个正数后遇到一个很大的负数和一下子掉下来然后又升上去。这种非单调性直接堵死了一条很多人第一反应会走的路滑动窗口。1.3 为什么滑动窗口在这道题上会失效滑动窗口双指针是处理连续子数组求和的经典工具比如“和无大于等于target的最短子数组”这类题。它之所以高效是因为窗口右边界往右扩展时窗口和变大左边界往右缩时窗口和变小。这个单调性保证了你移动指针的每一步都有明确方向。但一旦数组里出现负数这个前提就破了。右指针往右走窗口和可能变小左指针往右走窗口和可能变大。这种情况下你没法确定该挪哪个指针即使挪对了也无法保证不会漏掉解。我见过不少人在这道题上试着用滑动窗口写写了半天发现样例都过不了最后才意识到负数把单调性破坏掉了。2. 从暴力到优雅优化路径拆解2.1 三层循环的暴力枚举最直觉的写法是枚举所有子数组。一个子数组由起点和终点决定所以我们可以写两层循环确定起点和终点然后第三层循环从起点加到终点计算总和。def subarraySum(nums, k): n len(nums) count 0 for i in range(n): for j in range(i, n): total 0 for m in range(i, j 1): total nums[m] if total k: count 1 return count三层循环最内层每次重新加一遍时间复杂度O(n³)。这个版本我一般不建议你真正提交它存在的意义是帮你确认自己理解了题意子数组是连续区间位置不同就算不同。三个循环分别对应“起点”、“终点”、“求和”逻辑很直白但效率极其低下n稍微大一点比如500以上就会超时。2.2 固定起点累加的O(n²)优化三层循环最蠢的地方在于每次内层都从零开始加。其实我们固定起点i之后让终点j不断往右走同时用一个变量维护当前这段的和就不需要第三层循环了。def subarraySum(nums, k): n len(nums) count 0 for i in range(n): total 0 for j in range(i, n): total nums[j] if total k: count 1 return count这个版本是O(n²)已经是很多人的第一版“能过一部分样例”的代码。它的核心思想是固定每个起点i然后依次增加终点j实时维护从i到j的区间和。每个片段的和只需要在上一个片段基础上加一个元素不用重新算。不过当n达到10⁵级别时O(n²)依然会超时LeetCode的测试用例显然会把它卡掉。2.3 暴力法的复杂度画像与瓶颈暴力法慢在哪慢在我们在反复求“从i到j这一段的和”。即使优化到O(n²)依然有太多冗余计算不同的起点和终点组合成大量区间很多区间是重叠的它们的和信息被反复计算。比如求nums[1..5]的和和求nums[1..4]的和只有最后一个元素不同但每次都要重新累加。这说明我们需要一种方式能快速算出任意区间的和而不是每次从头加到尾。这时候前缀和就该登场了。前缀和的核心思想是提前算好“从数组开头到每个位置”的累计和那么任意区间[i, j]的和就等于pre[j1] - pre[i]直接两个数相减O(1)拿到结果。3. 前缀和 哈希表O(n)解法全解析3.1 前缀和的数学表达定义前缀和数组pre其中pre[i]表示原数组nums[0..i-1]所有元素的和也就是“前i个元素的和”。特别地pre[0] 0代表一个元素都不取时的和。有了这个定义任意一个子数组nums[i..j]的和可以表示为subarray_sum(i, j) pre[j1] - pre[i]我们要找的是subarray_sum(i, j) k代入就变成pre[j1] - pre[i] k移项pre[i] pre[j1] - k这个移项是整个题目的灵魂。它把“找区间和等于K”的问题变成了“找两个前缀和之间的差值等于K”的问题。也就是说当我们遍历到右端点j对应前缀和位置j1时只需要看看之前有没有出现过值为pre[j1] - k的前缀和。如果有每出现一次就说明有一个左端点 i 能和当前右端点组成一个满足条件的子数组。3.2 哈希表里存的是“次数”而非“下标”很多做“和为K的最长子数组”LeetCode 325的朋友会习惯性在哈希表里存下标但这道题要存的是次数。因为题目只问有多少个子数组不问最长或最短所以对于某个前缀和值我们只关心它出现过几次不关心它第一次出现在哪。为什么是次数假设当前前缀和是pre我们想找有没有pre - k出现过。如果pre - k出现过3次那就意味着有3个不同的左端点能和当前右端点构成合法的子数组。这3个子数组的区间不同都要计入答案所以哈希表的值必须是次数。def subarraySum(nums, k): mp {0: 1} pre_sum 0 count 0 for num in nums: pre_sum num count mp.get(pre_sum - k, 0) mp[pre_sum] mp.get(pre_sum, 0) 1 return count核心就三行逻辑累加当前前缀和查哈希表找pre_sum - k的计数并累加到答案再把当前前缀和的出现次数加一。整个遍历一趟数组时间复杂度O(n)空间复杂度O(n)。3.3 手推示例nums[1,1,1] 的全过程光看代码不够我建议你亲手推一遍。以nums [1, 1, 1]k 2为例初始化mp {0: 1}pre_sum 0count 0第一个元素1pre_sum 1查mp[1-2] mp[-1]不存在于是count 0。更新mp[1] 1此时mp {0:1, 1:1}第二个元素1pre_sum 2查mp[2-2] mp[0]存在且为1count 1。更新mp[2] 1第三个元素1pre_sum 3查mp[3-2] mp[1]存在且为1count 2。更新mp[3] 1最终返回2和预期一致。注意到第二个元素时查到的mp[0]对应的左端点是“空前缀”也就是从数组开头到当前位置的整个子数组这正说明初始化mp[0] 1是必须的。再推一个带负数的例子nums [1, -1, 0]k 0。这个例子能同时验证负数场景和连续0的情况答案是3[1, -1]、[0]、[1, -1, 0]。初始化mp {0: 1}pre_sum 0count 0第一个元素1pre_sum 1查mp[1-0] mp[1]无count 0。更新mp[1] 1第二个元素-1pre_sum 0查mp[0-0] mp[0]有1count 1这里对应子数组[1,-1]。更新mp[0] 2第三个元素0pre_sum 0查mp[0-0] mp[0]有2count 3对应子数组[0]和[1,-1,0]。更新mp[0] 3完美得到3。这里的第二个元素处如果初始mp[0]不是1就会漏掉[1,-1]这个从开头开始的子数组。第三个元素处利用mp[0] 2一次统计了两条子数组效率非常高。3.4 关键细节为什么“先查询后更新”这是这道题最容易被忽略的细节。每遍历一个元素必须先查mp[pre_sum - k]然后才能把当前pre_sum计数的频率加一。如果你反过来先更新mp[pre_sum]再查询会导致什么样的后果当k 0时pre_sum - k恰好等于pre_sum。如果你先把当前pre_sum加进哈希表再查询就会把“当前这个前缀和自身”也当成一个答案统计进去。但当前这个位置还没结束它不能既当左端点又当右端点。举最极端的例子nums [2]k 0。正确答案是0因为没有任何子数组和为0。但如果你先更新再查询pre_sum 2mp[2] 1查mp[2-0] 1得到count 1直接算错了。“先查后更新”本质上是保证左右端点不能重合。查询时哈希表里只包含当前元素之前的前缀和这才能保证左端点 i 严格小于当前右端点 j。4. 边界情况与实战坑位4.1 K0时最容易漏统计的场景上一节提到了k 0的情况这里再展开说透。当K等于0时题目变成有多少个子数组的和等于0。因为零的特殊性答案常常比直觉多很多。比如nums [0, 0]K0正确答案是3两个单独为0的子数组加上整个数组[0,0]。用哈希表方案可以轻松算出来。但如果你是手动模拟暴力很可能只数出2个。这个例子也很适合拿来测试你自己的写法如果输出1或2说明你的初始化或更新逻辑有问题。注意K0时pre_sum - k等于pre_sum本身这要求查询时绝对不能把当前刚更新的前缀和算进去。一旦先更新再查询错误会立刻暴露。4.2 负数与零对前缀和的影响负数导致前缀和不单调这是滑动窗口失效的根源。零则导致前缀和可能出现连续重复值这对计数没有坏处因为重复值越多哈希表里mp[pre_sum]越大后面遇到匹配时能一次性统计更多答案。但重复前缀和也会让一个直觉性结论变得反直觉一个子数组的和为0不一定是[0]或[1,-1]这样的直观组合它可能藏在连续多个0里比如[0,0,0]的子数组和为0的有6条。哈希表方案的好处是遇到重复的pre_sum直接把计数累加进哈希表后续匹配时一次拿全不会漏。4.3 细节决定成败初始值、变量类型与语言陷阱初始化mp {0: 1}的作用是支持“从数组开头开始的子数组”。任何前缀和pre_sum - k 0的情况都意味着存在一个从下标0开始到当前右端点结束的子数组。如果不初始化这样的子数组会被全部漏掉而且在K0时错误尤其隐蔽。变量类型方面Python的int是任意精度不需要担心溢出。但如果你用Java或C前缀和累加可能会超过int范围。数组长度最大是2 * 10⁵每个元素绝对值最大10⁴前缀和绝对值最大能到2 * 10⁹虽然int最大约2.1 * 10⁹看起来刚好卡在边界但多个累加中间过程可能超过稳妥起见建议直接用long。LeetCode原题的函数签名返回int但累加变量pre_sum和答案count都应该用更大的类型Java用long和longC用long long。注意答案可能超过int范围。极端情况下数组全为0K0子数组数量是 n * (n1) / 2n210⁵ 时大约210¹⁰远超int范围。Python没有这个问题Java和C需要特别留意答案类型。5. 变体与面试延伸5.1 如果面试官要求输出所有满足条件的子数组有时候面试官会在你写完后追问能不能把所有满足条件的子数组打印出来这时候哈希表里存的就不能只是次数了而是一个数组记录每个前缀和出现过的下标。基本思路mp[pre_sum]改成mp[pre_sum] [下标列表]。遍历时查到pre_sum - k对应的下标列表后列表里每个下标 i 都和当前右端点构成一个合法子数组nums[i1..j]。注意当前pre_sum对应的右端点下标是j而pre_sum本身是在元素nums[j]累加后得到的所以区间起点是i1终点是j。def subarraySumDetails(nums, k): mp {0: [-1]} pre_sum 0 res [] for j, num in enumerate(nums): pre_sum num target pre_sum - k if target in mp: for i in mp[target]: res.append((i 1, j)) mp.setdefault(pre_sum, []).append(j) return res注意这里初始化{0: [-1]}因为前缀和pre[0]对应“一个元素都不取”当我们需要i -1时子数组从下标0开始。这个变体是很好的加分项面试官能看出你是真的理解了这个方法而不是背代码。5.2 与同类题目的对比974、325、862面试中面试官很可能借这道题引出一系列姊妹题。我整理过一个对比清单这里分享给你题目要求哈希表存什么关键差异560 和为K的子数组计数前缀和出现次数先查后更新初始{0:1}325 和为K的最长子数组最长前缀和最早出现的下标需要存下标且只存最早一次974 和可被K整除的子数组计数前缀和余数出现次数负数取模需要调整C里要加K再模862 和至少为K的最短子数组最短单调双端队列有负数用前缀和单调队列维护974题与560几乎同构只差一个取模。要注意的是负数取模在不同语言里行为不同C中(-5) % 3 -2需要写成((pre_sum % k) k) % k统一余数范围。这些姊妹题能让你形成完整的知识网络遇到类似题时能迅速识别模式。5.3 这道题在工作场景中的映射很多朋友问算法题到底有什么用其实前缀和思想在工程里非常常见。比如分析交易流水想知道有多少个连续时间段内的累计交易额正好等于某个目标值或者分析日志数据找出一段连续请求量的和是否命中某个阈值。这些场景本质上都是“区间求和 条件计数”。更进一步任何需要频繁计算任意区间和的场景前缀和都是利器。预计算一遍前缀和数组之后每次区间查询都是O(1)的减法操作。这在报表系统、数据分析和监控告警系统中都很实用。6. 踩坑记录与个人心得6.1 我实际提交时遇到过的错误第一次写这道题我犯过三个典型错误每个都值得拿出来说。第一个是忘记初始化mp[0] 1结果所有从下标0开始的子数组全部漏掉。当时我用nums [3, 4, 7, 2, -3, 1, 4, 2]这样的用例测试一直少算了[3, 4]这样的开头子数组查了十几分钟才发现哈希表里根本没有0。第二个是只想着存下标写成了mp {0: -1}然后试图用j - i来计数写出来的代码又臭又长还漏了重复前缀和的情况。后来才意识到这道题根本不需要下标存次数就够了。第三个是在处理负数取模的时候一开始没把余数归一导致974题怎么都不对。从那以后我养成了一个习惯遇到取模运算先确认负数的语义。6.2 解题前必做的“三问”现在我做连续子数组求和类的题目动笔之前会先做三个自问自答一数组里有没有负数有负数滑窗基本可以排除无负数滑窗可以作为一个候选方案。 二题目要的是计数、最长、最短还是打印所有子数组这决定了哈希表里存次数、最早下标还是下标列表。 三当前遍历位置能否参与答案统计也就是“先查后更新”的顺序问题。这个顺序在所有类似题目里都要留意不只是K0时才需要。这套三问法让我少踩了很多坑也让我在面试时能更清晰地给面试官讲思路。6.3 最后一点经验回过头看560这道题难吗知识点本身不难前缀和和哈希表都是基础内容。但它之所以被放进Hot 100我猜是因为它把“连续区间求和”“哈希表优化”“边界条件处理”三个高频考点浓缩到了一道题里。你能不能在紧张的环境下一步步推导出O(n)方案能不能正确处理负数和零能不能讲清楚先查后更新的道理往往比代码本身更能反映水平。我自己后来刷题时只要遇到“连续子数组 和/积 计数”的组合第一反应就是先想想能不能用前缀和如果题目允许负数和零基本上可以确定哈希表方案是正解。这个条件反射帮我解决了不少Hard题的基础版本。希望你也能通过这道题把前缀和 哈希表这套思路真正变成自己的东西。