如果你正在刷 LeetCode 热题 100做到第 560 题“和为 K 的子数组”时第一反应八成是这题不是很简单吗等到提交之后看到一堆红色错误才开始怀疑人生。这道题表面上是“求子数组的和等于某个目标值”实际考察的是前缀和思想加哈希表压缩时间复杂度的能力。它不算难但特别容易掉进三个坑误用滑动窗口、漏掉负数场景、忽略了计数型题目对历史状态的统计方式。这篇内容适合正在准备校招、社招算法面或者刚把 hot 100 刷到一半想彻底搞懂这类题的同学。我会把从暴力枚举到前缀和再到哈希表优化的完整进化链路拆开讲清楚每一步都说明“为什么要这么做”并附上多语言代码、边界场景分析和变体题目扩展。看完你不仅能 AC 这题还能顺手解决一大票“连续子数组 计数/最大长度”的同类题。1. 题目解读与整体思路拆解1.1 子数组连续、非空、顺序不变先确认题目在研究什么东西。给定一个整数数组 nums 和一个整数 k需要统计有多少个连续的子数组其元素和等于 k。这里的“子数组”三个字非常关键。它与“子序列”的区别在于子数组必须是原数组中连续的一段不能跳元素子序列则允许跳过中间的元素只要相对顺序保持一致。举个最直白的例子nums [1, 2, 3]那么它的子数组只有 [1]、[2]、[3]、[1,2]、[2,3]、[1,2,3] 这六种而 [1,3] 不是子数组只是子序列。这一条直接决定了后面所有算法的形态我们枚举的是起点和终点而不是哪些元素被选中。题目还要求返回的是满足条件的子数组的“个数”而不是是否存在也不是最长的长度。这个细节非常容易在脑子里被默认忽略。很多第一次做的人会下意识按“判断有没有和为 k 的子数组”去解然后写出了一个可以提前 break 的代码结果发现答案是错的。因为我们要的是所有满足条件的区间哪怕有完全相同的元素组合从不同位置开始都要分别计数。最后还有一个隐性约束子数组是非空的。这一点后面讲边界条件时会详细展开它直接关系到哈希表的初始化方式。1.2 数据范围在暗示什么原题中 nums 的长度最大为 2×10^4元素值范围为 [-1000, 1000]目标 k 在 [-10^7, 10^7] 内。这个数据范围本身就是提示。如果长度只有几百三重循环虽然丑但也能交当长度到了两万时任何 O(n^2) 级别的算法在最坏情况下都是 4×10^8 次操作在 Python 里基本要跑数秒甚至更久Java 和 C 也许能勉强过但绝对不是理想解法。热题 100 里的题目大多有“引导你用更优思路”的性质所以看到这个规模第一反应就应该是要找一种 O(n) 或 O(n log n) 的算法。而“连续子数组 区间和 计数”这个组合几乎就是前缀和的招牌场景。1.3 为什么这题值得进热题 100从面试角度来说这题能在一道题里考察好几个层次第一层会不会暴力解至少能看出你是否理解子数组定义第二层知不知道前缀和优化区间求和第三层能不能想到用哈希表把双循环再压成单循环第四层能不能说清楚为什么不能用滑动窗口、以及哈希表初始化和更新顺序这些细节。面试官完全可以顺着这一道题从浅问到深把候选人的算法功底摸得比较透。从刷题角度来说它又是“前缀和 哈希表”这一类问题的最小完整样本理解透这一题之后再遇到“和为 K 的最长子数组长度”“和可被 K 整除的子数组数量”这类变体迁移成本很低。2. 从暴力到前缀和优化路径是怎么长出来的2.1 第一版三重循环暴力枚举最朴素的思路是枚举所有可能的区间起点 i 和终点 j然后对区间 [i, j] 内所有元素求和判断是否等于 k。因为子数组总数是 O(n^2) 个每个区间求和又需要 O(n)整体就是 O(n^3)。用 Python 写出来大概是def subarray_sum_bruteforce(nums, k): n len(nums) ans 0 for i in range(n): for j in range(i, n): current_sum 0 for m in range(i, j 1): current_sum nums[m] if current_sum k: ans 1 return ans这版代码的问题显而易见大量区间重复累加同一个元素浪费严重。比如 [0, 2] 区间和 [0, 3] 区间在暴力做法里 [0, 2] 的和会被重新算一遍。它的意义只有一个帮你确认自己理解题目。实际笔试或面试中你可以在开头提一句“如果数据量小可以这样做”然后立刻转向更好的方案。但不要把它作为最终答案交上去。2.2 第二版前缀和把区间和变成两个累计值之差前缀和的思想其实特别简单维护一个数组 prefix其中 prefix[i] 表示原数组前 i 个元素的和也就是 nums[0] nums[1] ... nums[i-1]。这样任意区间 [left, right]left right采用前闭后闭的和就能写成sum(left, right) prefix[right 1] - prefix[left]这个公式没有任何魔法它就是两个累计值相减相当于你记账时想知道某一个月花了多少钱只需看月底累计支出和上个月底的累计支出之差。用这样的方式我们就把“子数组的和等于 k”这个条件等价地变成“两个前缀和的差等于 k”。基于这个公式可以写出 O(n^2) 的第二版def subarray_sum_prefix(nums, k): n len(nums) prefix [0] * (n 1) for i in range(n): prefix[i 1] prefix[i] nums[i] ans 0 for left in range(n): for right in range(left, n): if prefix[right 1] - prefix[left] k: ans 1 return ans这版比三重循环好的地方在于每个前缀和只算一次之后查区间和是 O(1) 的。整体复杂度是 O(n^2)因为仍然要枚举所有左右端点组合。到这里你已经完成了“暴力 → 预处理”的第一次升级两万数据规模下大概率依旧过不了所有强测用例但思路已经在对的路上了。2.3 为什么不能直接上滑动窗口很多刷过“无重复字符的最长子串”“长度最小的子数组”的同学遇到这题的第一反应是双指针滑动窗口。但这里要非常严肃地说只要数组里有负数滑动窗口对于“求和等于目标值”这类问题就不成立。滑动窗口能高效的前提是窗口收缩时有明确的单调性比如求“和 target 的最短子数组”当和超过目标时右移左指针一定能让窗口和变小因为元素都是正数或非负数。可这道题的 nums 允许负数窗口扩张时和可能下降窗口收缩时和可能上升你完全无法判断该移动左指针还是右指针才能逼近 k。举个例子nums [-1, 3, -2, 1]k 1。从左到右滑动时窗口和的变化完全不是单调的[-1] 的和是 -1[-1, 3] 的和是 2[-1, 3, -2] 的和是 0你既不能因为当前和小于 k 就盲目右扩也不能因为当前和大于 k 就盲目左缩。这道题最经典的一个误导点就在这理解了它你就比很多一上来就写双指针的人强了。3. 哈希表优化把 O(n^2) 压成 O(n)3.1 核心等式的一次变形回到前缀和的公式。假设 prefix 是一个长度为 n1 的数组prefix[i] 表示前 i 个元素的和i 从 0 开始prefix[0] 0。我们要求的是prefix[right 1] - prefix[left] k改写一下prefix[right 1] - k prefix[left]也就是说当我们从左到右扫描数组、维护当前累计和 prefix[j] 的时候我们其实是在问在 j 之前的那些前缀和里有没有出现过 prefix[j] - k 这个值出现过几次就有多少个以当前位置为右端点、和为 k 的子数组。这句话是整个题解的灵魂。它把“同时枚举左右端点”的问题变成了“边扫描边查历史记录”的问题。我们不再需要知道左端点在哪个具体位置只需要知道左端点对应的前缀和出现过多少次。这个思路和“两数之和”把 a b target 改写成 a target - b 的做法如出一辙本质上都是通过等式变形把二维查找降成一维查找。3.2 哈希表里到底存什么哈希表的键是前缀和的值值是该前缀和值出现过的次数。从左到右遍历 nums每次累加出一个新的当前前缀和 cur_sum 时先查一下 cur_sum - k 在哈希表里有没有有的话就把对应的次数累加到答案里最后再把 cur_sum 自己放进哈希表次数加一。这里有三个容易被忽略的细节。第一哈希表初始化时要放入 {0: 1}。因为 prefix[0] 0也就是“一个元素都没取”时的前缀和。这个 0 存在的意义是当 cur_sum 本身就是 k 时cur_sum - k 0我们需要能查到它才能统计出“从数组开头到当前位置的整个前缀”作为完整子数组这个答案。试想 nums [1, 2, 3]k 3。遍历到第 2 个元素时cur_sum 3如果不初始化 0就查不到 cur_sum - k 0会把 [1, 2] 这个子数组漏掉。第二必须先查哈希表再把当前 cur_sum 插入哈希表。因为当前 cur_sum 对应的前缀是“到当前位置为止”的和它不能和自己组成长度为 0 的空区间。如果先插入再查询遇到 k 0 时就会多统计一个空区间。后面我会用具体例子演示这个 bug。第三哈希表记录的是“次数”而不是“下标”。因为题面要求统计的是子数组的个数同一个前缀和可能在数组的不同位置重复出现每次都对应一个不同的左端点候选所以要累加次数。如果你看到有人把哈希表的值存成下标数组那他大概率是在套最长子数组那类题的做法要小心区分。3.3 手动走一遍示例用题目自带的例子 nums [1, 2, 3]k 3 来完整走一遍算法初始化 map {0: 1}ans 0cur_sum 0。读取 1cur_sum 1。cur_sum - k -2不在 map 中。插入 map{0:1, 1:1}。此时以第 0 个元素结尾的子数组和为 3 的数量为 0。读取 2cur_sum 3。cur_sum - k 0在 map 中且次数为 1ans 1ans 1。这个 0 对应的是 prefix[0]也就是从数组开头到当前下标的区间 [0, 1]1 2 3。插入 map{0:1, 1:1, 3:1}。读取 3cur_sum 6。cur_sum - k 3在 map 中且次数为 1ans 1ans 2。这里的 3 对应 prefix[2]也就是区间 [2, 2]即单独的元素 3。插入 map{0:1, 1:1, 3:1, 6:1}。最终答案就是 2。整个过程中没有出现任何“回退”操作每个元素最多被访问两次一次求和、一次哈希查找所以时间复杂度是 O(n)。再走一个常见的重复样例 nums [1, 1, 1]k 2初始 {0:1}cur_sum 0ans 0。读取第一个 1cur_sum 1cur_sum - k -1 不在插入 {0:1, 1:1}。读取第二个 1cur_sum 2cur_sum - k 0 在ans 1插入 {0:1, 1:1, 2:1}。这个 0 对应前缀 0即区间 [0,1]前两个元素1 1 2。读取第三个 1cur_sum 3cur_sum - k 1 在ans 2插入 {0:1, 1:1, 2:1, 3:1}。这个 1 对应前缀 1即区间 [1,2]后两个元素1 1 2。最终 ans 2完美匹配预期。4. 最容易踩的边界坑从初始化到更新顺序4.1 当 k 0 时map 里的同一个键会反复出现很多跑不过的提交是在 k 0 的场景下挂掉的。举例 nums [1, -1, 0]k 0。正确的结果是 3子数组 [1, -1]、[1, -1, 0]、[0] 的和都为 0。用我们上面的算法走一遍初始化 {0: 1}cur_sum 0ans 0。i 0读取 1cur_sum 1。查 cur_sum - k 1不在。插入 map{0:1, 1:1}。i 1读取 -1cur_sum 0。查 cur_sum - k 0次数为 1ans 1。这个 1 对应之前出现过的 prefix[0] 0代表子数组 [1, -1]下标 0 到 1。插入当前 0map[0] 变成 2{0:2, 1:1}。i 2读取 0cur_sum 0。查 cur_sum - k 0此时 map[0] 为 2ans 1 2 3。这两个 0 分别代表 prefix[0] 和 prefix[2]分别对应子数组 [1, -1, 0]下标 0 到 2和 [0]下标 2 到 2。能看到关键在于 map 里记录的是历史 prefix 出现的“次数”同一个值出现多次意味着有多个不同的左端点候选。当你需要“计数”时用次数累加是天经地义的。4.2 如果先插入再查询会多算一个空区间回到那个容易写错的顺序问题。假设 nums [5]k 0正确结果显然是 0因为没有任何非空子数组的和是 0。我们的正确做法是cur_sum 5先查 5 - 0 5 是否在 map 中发现不在再插入 5所以答案是 0。如果你把顺序写反先执行 map.put(cur_sum, ...)再执行查询那么 cur_sum 5 时map 里刚刚出现了 55 - 0 5 能被查出来ans 被错误地加 1输出变成 1。这个 bug 非常隐蔽因为很多用例下先插入后查询也能碰巧正确只有 k 0 时才会稳定暴露。所以请务必养成“先查询、后更新”的习惯它不只是风格问题而是正确性问题。4.3 负数并不可怕它只是禁止滑动窗口有些同学看到题目有负数第一反应是“这题我不会了”。其实负数恰恰是哈希表解法擅长的场景因为前缀和数组里正负都能存哈希查找只看键是否存在跟值的大小符号无关。真正需要因为你预判错而警惕的是“能不能用双指针”的判断只有数组全部为非负数时滑动窗口的单调性才成立只要允许负数窗口和就在上下乱跳双指针失效。因此这题的数据设计其实是在逼你选择前缀和路线。另外关于溢出。按照本题的数据范围前缀和最大也就是 2×10^4 × 1000 2×10^7int 完全装得下。但如果你在刷题平台上见过数据范围更大的同类题或者自己在做扩展项目时遇到超大数值记得考虑用 long 或 long long 来存前缀和。这个细节不强制但很体现工程素养。5. 多语言实现与复杂度对照5.1 Java 版本public int subarraySum(int[] nums, int k) { MapInteger, Integer prefixCount new HashMap(); prefixCount.put(0, 1); int curSum 0; int ans 0; for (int num : nums) { curSum num; if (prefixCount.containsKey(curSum - k)) { ans prefixCount.get(curSum - k); } prefixCount.put(curSum, prefixCount.getOrDefault(curSum, 0) 1); } return ans; }5.2 Python 版本def subarraySum(self, nums: List[int], k: int) - int: prefix_count {0: 1} cur_sum 0 ans 0 for num in nums: cur_sum num if cur_sum - k in prefix_count: ans prefix_count[cur_sum - k] prefix_count[cur_sum] prefix_count.get(cur_sum, 0) 1 return ans5.3 C 版本int subarraySum(vectorint nums, int k) { unordered_mapint, int prefixCount; prefixCount[0] 1; int curSum 0, ans 0; for (int num : nums) { curSum num; if (prefixCount.find(curSum - k) ! prefixCount.end()) { ans prefixCount[curSum - k]; } prefixCount[curSum]; } return ans; }三个版本的核心逻辑完全一致都是同一个模板。实际提交时需要注意Java 中 HashMap 的查询和插入都是期望 O(1)Python 的 dict 同理C 的 unordered_map 在极端哈希碰撞情况下可能退化但 LeetCode 的测试数据通常不会刻意构造碰撞用起来没问题。5.4 复杂度对比算法时间复杂度空间复杂度能否通过两万数据暴力三重循环O(n^3)O(1)否前缀和 双循环O(n^2)O(n)勉强 / 不稳前缀和 哈希表O(n)O(n)是实际在线评测时前缀和 哈希表版本在 Python 下跑 2×10^4 长度数组耗时一般在几十毫秒级别Java/C 更快差别不大。空间上多维护一个哈希表最坏情况下里面可能有 n1 个不同键所以空间复杂度 O(n)。如果你追求极致内存可以考虑在某些场景下用数组模拟前缀统计但哈希表是通用且代码最简洁的方案。6. 变体与扩展一个模板打穿一类题6.1 和为 K 的最长子数组长度把“计数”改成“求最大长度”模板只需要微调哈希表记录某个前缀和第一次出现的下标而不是次数。遍历时如果 cur_sum - k 在哈希表里且之前出现过就尝试用当前下标减去历史下标更新答案同时只有当前 cur_sum 还没在哈希表里出现过时才把它放进去因为最早的相同前缀和才能保证子数组更长。核心区别就是 map 的 value 从 count 变成了 index且更新时机变成了“首次出现才写入”。6.2 连续数组0 和 1 数量相等的最长连续数组LeetCode 525 题要求找 0 和 1 数量相等的最长子数组。处理方法很经典把 0 当作 -1 来统计前缀和那么“0 和 1 数量相等”就等价于“前缀和相等”。找两个相同前缀和之间的最大距离即可。这题就是前缀和 哈希表模板在“转化条件”上的应用当你学会把相等数量关系转化为 1/-1 前缀和时题目难度立刻降了一个维度。6.3 矩阵里的子矩阵目标和如果题目从一维数组升级成二维矩阵要求统计有多少个子矩阵的元素和等于目标值核心思路仍然是前缀和只是要先枚举上下边界把多行压成一行再在一维上跑本文的模板。LeetCode 1074 就是这么一题它把“二维问题”降维成“多轮一维问题”每一步都可以复用我们这里推导过的算法。理解了 560 题再去看 1074 会非常顺畅因为框架没变只是多了一层边界枚举。这类变体还有很多比如“和可被 K 整除的子数组数量”“和为 K 的最小子数组长度”等等。你会发现它们的共同套路惊人一致连续子数组 和/差值条件 → 前缀和变形 → 哈希表压缩。刷题时不要把每一题当成孤立的新题而是抓住这个模板再针对具体条件做微调效率会高很多。说实话这道题我第一次做也栽在滑动窗口上当时心想“这不是和 209. 长度最小的子数组一模一样吗”结果写完提交负数样例直接教做人。后来把前缀和和哈希表两条线彻底理顺之后才发现这类题其实都有同一个影子遇到连续子数组的问题先想前缀和能不能表达条件再想哈希表能不能把查找历史变成 O(1)。这个思考链路本身就是热题 100 想让你练出来的东西所以 560 虽然只是一道 medium我的建议是把它当成一道 hard 级别的思想题去复盘几遍顺便把 525、974、1074 一起刷了。最后再提一个小技巧面试时不要直接甩最优解先从暴力说起再说前缀和最后才上哈希表把每一步“为什么需要优化”讲清楚面试官往往会对你更满意。
前缀和与哈希表：高效解决LeetCode 560和为K的子数组
如果你正在刷 LeetCode 热题 100做到第 560 题“和为 K 的子数组”时第一反应八成是这题不是很简单吗等到提交之后看到一堆红色错误才开始怀疑人生。这道题表面上是“求子数组的和等于某个目标值”实际考察的是前缀和思想加哈希表压缩时间复杂度的能力。它不算难但特别容易掉进三个坑误用滑动窗口、漏掉负数场景、忽略了计数型题目对历史状态的统计方式。这篇内容适合正在准备校招、社招算法面或者刚把 hot 100 刷到一半想彻底搞懂这类题的同学。我会把从暴力枚举到前缀和再到哈希表优化的完整进化链路拆开讲清楚每一步都说明“为什么要这么做”并附上多语言代码、边界场景分析和变体题目扩展。看完你不仅能 AC 这题还能顺手解决一大票“连续子数组 计数/最大长度”的同类题。1. 题目解读与整体思路拆解1.1 子数组连续、非空、顺序不变先确认题目在研究什么东西。给定一个整数数组 nums 和一个整数 k需要统计有多少个连续的子数组其元素和等于 k。这里的“子数组”三个字非常关键。它与“子序列”的区别在于子数组必须是原数组中连续的一段不能跳元素子序列则允许跳过中间的元素只要相对顺序保持一致。举个最直白的例子nums [1, 2, 3]那么它的子数组只有 [1]、[2]、[3]、[1,2]、[2,3]、[1,2,3] 这六种而 [1,3] 不是子数组只是子序列。这一条直接决定了后面所有算法的形态我们枚举的是起点和终点而不是哪些元素被选中。题目还要求返回的是满足条件的子数组的“个数”而不是是否存在也不是最长的长度。这个细节非常容易在脑子里被默认忽略。很多第一次做的人会下意识按“判断有没有和为 k 的子数组”去解然后写出了一个可以提前 break 的代码结果发现答案是错的。因为我们要的是所有满足条件的区间哪怕有完全相同的元素组合从不同位置开始都要分别计数。最后还有一个隐性约束子数组是非空的。这一点后面讲边界条件时会详细展开它直接关系到哈希表的初始化方式。1.2 数据范围在暗示什么原题中 nums 的长度最大为 2×10^4元素值范围为 [-1000, 1000]目标 k 在 [-10^7, 10^7] 内。这个数据范围本身就是提示。如果长度只有几百三重循环虽然丑但也能交当长度到了两万时任何 O(n^2) 级别的算法在最坏情况下都是 4×10^8 次操作在 Python 里基本要跑数秒甚至更久Java 和 C 也许能勉强过但绝对不是理想解法。热题 100 里的题目大多有“引导你用更优思路”的性质所以看到这个规模第一反应就应该是要找一种 O(n) 或 O(n log n) 的算法。而“连续子数组 区间和 计数”这个组合几乎就是前缀和的招牌场景。1.3 为什么这题值得进热题 100从面试角度来说这题能在一道题里考察好几个层次第一层会不会暴力解至少能看出你是否理解子数组定义第二层知不知道前缀和优化区间求和第三层能不能想到用哈希表把双循环再压成单循环第四层能不能说清楚为什么不能用滑动窗口、以及哈希表初始化和更新顺序这些细节。面试官完全可以顺着这一道题从浅问到深把候选人的算法功底摸得比较透。从刷题角度来说它又是“前缀和 哈希表”这一类问题的最小完整样本理解透这一题之后再遇到“和为 K 的最长子数组长度”“和可被 K 整除的子数组数量”这类变体迁移成本很低。2. 从暴力到前缀和优化路径是怎么长出来的2.1 第一版三重循环暴力枚举最朴素的思路是枚举所有可能的区间起点 i 和终点 j然后对区间 [i, j] 内所有元素求和判断是否等于 k。因为子数组总数是 O(n^2) 个每个区间求和又需要 O(n)整体就是 O(n^3)。用 Python 写出来大概是def subarray_sum_bruteforce(nums, k): n len(nums) ans 0 for i in range(n): for j in range(i, n): current_sum 0 for m in range(i, j 1): current_sum nums[m] if current_sum k: ans 1 return ans这版代码的问题显而易见大量区间重复累加同一个元素浪费严重。比如 [0, 2] 区间和 [0, 3] 区间在暴力做法里 [0, 2] 的和会被重新算一遍。它的意义只有一个帮你确认自己理解题目。实际笔试或面试中你可以在开头提一句“如果数据量小可以这样做”然后立刻转向更好的方案。但不要把它作为最终答案交上去。2.2 第二版前缀和把区间和变成两个累计值之差前缀和的思想其实特别简单维护一个数组 prefix其中 prefix[i] 表示原数组前 i 个元素的和也就是 nums[0] nums[1] ... nums[i-1]。这样任意区间 [left, right]left right采用前闭后闭的和就能写成sum(left, right) prefix[right 1] - prefix[left]这个公式没有任何魔法它就是两个累计值相减相当于你记账时想知道某一个月花了多少钱只需看月底累计支出和上个月底的累计支出之差。用这样的方式我们就把“子数组的和等于 k”这个条件等价地变成“两个前缀和的差等于 k”。基于这个公式可以写出 O(n^2) 的第二版def subarray_sum_prefix(nums, k): n len(nums) prefix [0] * (n 1) for i in range(n): prefix[i 1] prefix[i] nums[i] ans 0 for left in range(n): for right in range(left, n): if prefix[right 1] - prefix[left] k: ans 1 return ans这版比三重循环好的地方在于每个前缀和只算一次之后查区间和是 O(1) 的。整体复杂度是 O(n^2)因为仍然要枚举所有左右端点组合。到这里你已经完成了“暴力 → 预处理”的第一次升级两万数据规模下大概率依旧过不了所有强测用例但思路已经在对的路上了。2.3 为什么不能直接上滑动窗口很多刷过“无重复字符的最长子串”“长度最小的子数组”的同学遇到这题的第一反应是双指针滑动窗口。但这里要非常严肃地说只要数组里有负数滑动窗口对于“求和等于目标值”这类问题就不成立。滑动窗口能高效的前提是窗口收缩时有明确的单调性比如求“和 target 的最短子数组”当和超过目标时右移左指针一定能让窗口和变小因为元素都是正数或非负数。可这道题的 nums 允许负数窗口扩张时和可能下降窗口收缩时和可能上升你完全无法判断该移动左指针还是右指针才能逼近 k。举个例子nums [-1, 3, -2, 1]k 1。从左到右滑动时窗口和的变化完全不是单调的[-1] 的和是 -1[-1, 3] 的和是 2[-1, 3, -2] 的和是 0你既不能因为当前和小于 k 就盲目右扩也不能因为当前和大于 k 就盲目左缩。这道题最经典的一个误导点就在这理解了它你就比很多一上来就写双指针的人强了。3. 哈希表优化把 O(n^2) 压成 O(n)3.1 核心等式的一次变形回到前缀和的公式。假设 prefix 是一个长度为 n1 的数组prefix[i] 表示前 i 个元素的和i 从 0 开始prefix[0] 0。我们要求的是prefix[right 1] - prefix[left] k改写一下prefix[right 1] - k prefix[left]也就是说当我们从左到右扫描数组、维护当前累计和 prefix[j] 的时候我们其实是在问在 j 之前的那些前缀和里有没有出现过 prefix[j] - k 这个值出现过几次就有多少个以当前位置为右端点、和为 k 的子数组。这句话是整个题解的灵魂。它把“同时枚举左右端点”的问题变成了“边扫描边查历史记录”的问题。我们不再需要知道左端点在哪个具体位置只需要知道左端点对应的前缀和出现过多少次。这个思路和“两数之和”把 a b target 改写成 a target - b 的做法如出一辙本质上都是通过等式变形把二维查找降成一维查找。3.2 哈希表里到底存什么哈希表的键是前缀和的值值是该前缀和值出现过的次数。从左到右遍历 nums每次累加出一个新的当前前缀和 cur_sum 时先查一下 cur_sum - k 在哈希表里有没有有的话就把对应的次数累加到答案里最后再把 cur_sum 自己放进哈希表次数加一。这里有三个容易被忽略的细节。第一哈希表初始化时要放入 {0: 1}。因为 prefix[0] 0也就是“一个元素都没取”时的前缀和。这个 0 存在的意义是当 cur_sum 本身就是 k 时cur_sum - k 0我们需要能查到它才能统计出“从数组开头到当前位置的整个前缀”作为完整子数组这个答案。试想 nums [1, 2, 3]k 3。遍历到第 2 个元素时cur_sum 3如果不初始化 0就查不到 cur_sum - k 0会把 [1, 2] 这个子数组漏掉。第二必须先查哈希表再把当前 cur_sum 插入哈希表。因为当前 cur_sum 对应的前缀是“到当前位置为止”的和它不能和自己组成长度为 0 的空区间。如果先插入再查询遇到 k 0 时就会多统计一个空区间。后面我会用具体例子演示这个 bug。第三哈希表记录的是“次数”而不是“下标”。因为题面要求统计的是子数组的个数同一个前缀和可能在数组的不同位置重复出现每次都对应一个不同的左端点候选所以要累加次数。如果你看到有人把哈希表的值存成下标数组那他大概率是在套最长子数组那类题的做法要小心区分。3.3 手动走一遍示例用题目自带的例子 nums [1, 2, 3]k 3 来完整走一遍算法初始化 map {0: 1}ans 0cur_sum 0。读取 1cur_sum 1。cur_sum - k -2不在 map 中。插入 map{0:1, 1:1}。此时以第 0 个元素结尾的子数组和为 3 的数量为 0。读取 2cur_sum 3。cur_sum - k 0在 map 中且次数为 1ans 1ans 1。这个 0 对应的是 prefix[0]也就是从数组开头到当前下标的区间 [0, 1]1 2 3。插入 map{0:1, 1:1, 3:1}。读取 3cur_sum 6。cur_sum - k 3在 map 中且次数为 1ans 1ans 2。这里的 3 对应 prefix[2]也就是区间 [2, 2]即单独的元素 3。插入 map{0:1, 1:1, 3:1, 6:1}。最终答案就是 2。整个过程中没有出现任何“回退”操作每个元素最多被访问两次一次求和、一次哈希查找所以时间复杂度是 O(n)。再走一个常见的重复样例 nums [1, 1, 1]k 2初始 {0:1}cur_sum 0ans 0。读取第一个 1cur_sum 1cur_sum - k -1 不在插入 {0:1, 1:1}。读取第二个 1cur_sum 2cur_sum - k 0 在ans 1插入 {0:1, 1:1, 2:1}。这个 0 对应前缀 0即区间 [0,1]前两个元素1 1 2。读取第三个 1cur_sum 3cur_sum - k 1 在ans 2插入 {0:1, 1:1, 2:1, 3:1}。这个 1 对应前缀 1即区间 [1,2]后两个元素1 1 2。最终 ans 2完美匹配预期。4. 最容易踩的边界坑从初始化到更新顺序4.1 当 k 0 时map 里的同一个键会反复出现很多跑不过的提交是在 k 0 的场景下挂掉的。举例 nums [1, -1, 0]k 0。正确的结果是 3子数组 [1, -1]、[1, -1, 0]、[0] 的和都为 0。用我们上面的算法走一遍初始化 {0: 1}cur_sum 0ans 0。i 0读取 1cur_sum 1。查 cur_sum - k 1不在。插入 map{0:1, 1:1}。i 1读取 -1cur_sum 0。查 cur_sum - k 0次数为 1ans 1。这个 1 对应之前出现过的 prefix[0] 0代表子数组 [1, -1]下标 0 到 1。插入当前 0map[0] 变成 2{0:2, 1:1}。i 2读取 0cur_sum 0。查 cur_sum - k 0此时 map[0] 为 2ans 1 2 3。这两个 0 分别代表 prefix[0] 和 prefix[2]分别对应子数组 [1, -1, 0]下标 0 到 2和 [0]下标 2 到 2。能看到关键在于 map 里记录的是历史 prefix 出现的“次数”同一个值出现多次意味着有多个不同的左端点候选。当你需要“计数”时用次数累加是天经地义的。4.2 如果先插入再查询会多算一个空区间回到那个容易写错的顺序问题。假设 nums [5]k 0正确结果显然是 0因为没有任何非空子数组的和是 0。我们的正确做法是cur_sum 5先查 5 - 0 5 是否在 map 中发现不在再插入 5所以答案是 0。如果你把顺序写反先执行 map.put(cur_sum, ...)再执行查询那么 cur_sum 5 时map 里刚刚出现了 55 - 0 5 能被查出来ans 被错误地加 1输出变成 1。这个 bug 非常隐蔽因为很多用例下先插入后查询也能碰巧正确只有 k 0 时才会稳定暴露。所以请务必养成“先查询、后更新”的习惯它不只是风格问题而是正确性问题。4.3 负数并不可怕它只是禁止滑动窗口有些同学看到题目有负数第一反应是“这题我不会了”。其实负数恰恰是哈希表解法擅长的场景因为前缀和数组里正负都能存哈希查找只看键是否存在跟值的大小符号无关。真正需要因为你预判错而警惕的是“能不能用双指针”的判断只有数组全部为非负数时滑动窗口的单调性才成立只要允许负数窗口和就在上下乱跳双指针失效。因此这题的数据设计其实是在逼你选择前缀和路线。另外关于溢出。按照本题的数据范围前缀和最大也就是 2×10^4 × 1000 2×10^7int 完全装得下。但如果你在刷题平台上见过数据范围更大的同类题或者自己在做扩展项目时遇到超大数值记得考虑用 long 或 long long 来存前缀和。这个细节不强制但很体现工程素养。5. 多语言实现与复杂度对照5.1 Java 版本public int subarraySum(int[] nums, int k) { MapInteger, Integer prefixCount new HashMap(); prefixCount.put(0, 1); int curSum 0; int ans 0; for (int num : nums) { curSum num; if (prefixCount.containsKey(curSum - k)) { ans prefixCount.get(curSum - k); } prefixCount.put(curSum, prefixCount.getOrDefault(curSum, 0) 1); } return ans; }5.2 Python 版本def subarraySum(self, nums: List[int], k: int) - int: prefix_count {0: 1} cur_sum 0 ans 0 for num in nums: cur_sum num if cur_sum - k in prefix_count: ans prefix_count[cur_sum - k] prefix_count[cur_sum] prefix_count.get(cur_sum, 0) 1 return ans5.3 C 版本int subarraySum(vectorint nums, int k) { unordered_mapint, int prefixCount; prefixCount[0] 1; int curSum 0, ans 0; for (int num : nums) { curSum num; if (prefixCount.find(curSum - k) ! prefixCount.end()) { ans prefixCount[curSum - k]; } prefixCount[curSum]; } return ans; }三个版本的核心逻辑完全一致都是同一个模板。实际提交时需要注意Java 中 HashMap 的查询和插入都是期望 O(1)Python 的 dict 同理C 的 unordered_map 在极端哈希碰撞情况下可能退化但 LeetCode 的测试数据通常不会刻意构造碰撞用起来没问题。5.4 复杂度对比算法时间复杂度空间复杂度能否通过两万数据暴力三重循环O(n^3)O(1)否前缀和 双循环O(n^2)O(n)勉强 / 不稳前缀和 哈希表O(n)O(n)是实际在线评测时前缀和 哈希表版本在 Python 下跑 2×10^4 长度数组耗时一般在几十毫秒级别Java/C 更快差别不大。空间上多维护一个哈希表最坏情况下里面可能有 n1 个不同键所以空间复杂度 O(n)。如果你追求极致内存可以考虑在某些场景下用数组模拟前缀统计但哈希表是通用且代码最简洁的方案。6. 变体与扩展一个模板打穿一类题6.1 和为 K 的最长子数组长度把“计数”改成“求最大长度”模板只需要微调哈希表记录某个前缀和第一次出现的下标而不是次数。遍历时如果 cur_sum - k 在哈希表里且之前出现过就尝试用当前下标减去历史下标更新答案同时只有当前 cur_sum 还没在哈希表里出现过时才把它放进去因为最早的相同前缀和才能保证子数组更长。核心区别就是 map 的 value 从 count 变成了 index且更新时机变成了“首次出现才写入”。6.2 连续数组0 和 1 数量相等的最长连续数组LeetCode 525 题要求找 0 和 1 数量相等的最长子数组。处理方法很经典把 0 当作 -1 来统计前缀和那么“0 和 1 数量相等”就等价于“前缀和相等”。找两个相同前缀和之间的最大距离即可。这题就是前缀和 哈希表模板在“转化条件”上的应用当你学会把相等数量关系转化为 1/-1 前缀和时题目难度立刻降了一个维度。6.3 矩阵里的子矩阵目标和如果题目从一维数组升级成二维矩阵要求统计有多少个子矩阵的元素和等于目标值核心思路仍然是前缀和只是要先枚举上下边界把多行压成一行再在一维上跑本文的模板。LeetCode 1074 就是这么一题它把“二维问题”降维成“多轮一维问题”每一步都可以复用我们这里推导过的算法。理解了 560 题再去看 1074 会非常顺畅因为框架没变只是多了一层边界枚举。这类变体还有很多比如“和可被 K 整除的子数组数量”“和为 K 的最小子数组长度”等等。你会发现它们的共同套路惊人一致连续子数组 和/差值条件 → 前缀和变形 → 哈希表压缩。刷题时不要把每一题当成孤立的新题而是抓住这个模板再针对具体条件做微调效率会高很多。说实话这道题我第一次做也栽在滑动窗口上当时心想“这不是和 209. 长度最小的子数组一模一样吗”结果写完提交负数样例直接教做人。后来把前缀和和哈希表两条线彻底理顺之后才发现这类题其实都有同一个影子遇到连续子数组的问题先想前缀和能不能表达条件再想哈希表能不能把查找历史变成 O(1)。这个思考链路本身就是热题 100 想让你练出来的东西所以 560 虽然只是一道 medium我的建议是把它当成一道 hard 级别的思想题去复盘几遍顺便把 525、974、1074 一起刷了。最后再提一个小技巧面试时不要直接甩最优解先从暴力说起再说前缀和最后才上哈希表把每一步“为什么需要优化”讲清楚面试官往往会对你更满意。
