1. 题目拆解先搞清楚“和为 K 的子数组”到底在问什么1.1 题目到底在说什么力扣 560 题“和为 K 的子数组”题目描述很简短给你一个整数数组nums和一个整数k请你统计并返回该数组中和为k的子数组的个数。这里有个关键点很多人第一次读题会忽略题目说的是子数组不是子序列。子数组意味着必须是连续的一段顺序不能乱也不能跳着选。比如nums [1, 2, 3]那么[1, 3]不算子数组因为 1 和 3 在原数组中不相邻[2, 3]才是合法的子数组。我举个具体的例子题目给定的示例是输入nums [1, 1, 1], k 2 输出2这个数组里和为 2 的连续子数组分别是[1, 1]下标 0 到 1和[1, 1]下标 1 到 2所以答案是 2。注意这两个子数组的元素值相同但下标范围不同算作两个不同的结果。再看一个稍微复杂点的例子输入nums [1, 2, 3], k 3 输出2这里的两个答案分别是[1, 2]下标 0 到 1和[3]下标 2 到 2。注意单个元素也可以作为子数组这个点在做边界判断时容易漏掉。还有一点值得提醒nums里的元素可以是负数。这会直接影响解法选择我后面会专门展开。很多人第一反应是“连续子数组求和那不就是滑动窗口吗”但正因为数组里有负数滑动窗口的双指针收缩策略会失效。这个坑我当年第一次做的时候也踩过。1.2 暴力解法的瓶颈所在最直观的解法就是枚举所有可能的子数组区间。假设数组长度为n任意一个子数组由左端点i和右端点j决定其中0 i j n。我只需要两重循环确定端点再计算这个区间的和和k相等就把计数加一。这里有三种计算区间和的方式它们的效率差别很大第一种是最朴素的每次枚举i和j之后再用一层循环从i加到j。这样是三层循环时间复杂度是O(n³)在力扣上连示例都要跑半天完全不可取。第二种是稍微优化一点固定左端点i然后让右端点j从i开始往右扩展一边扩展一边累加这样sum(i, j)就可以利用上一次的sum(i, j - 1)结果。代码写起来大概是int count 0; for (int i 0; i nums.size(); i) { int sum 0; for (int j i; j nums.size(); j) { sum nums[j]; if (sum k) count; } }这样降到了O(n²)思路非常直白没有任何技巧。但问题也很明显当n到10^5量级时n²就是10^10次运算在力扣的评测环境下基本会超时。第三种就是用前缀和数组预处理把任意区间和的计算变成O(1)但枚举区间仍然是O(n²)总复杂度还是O(n²)。前缀和的思路本身非常有价值它也是哈希表优化方案的基石所以我把它放在下一节单独讲。1.3 为什么不能用滑动窗口/双指针我见过不少人在评论区问“这题不是用滑动窗口就能做吗”如果你也这么想请先停下来想一个问题滑动窗口的可行性前提是什么滑动窗口最经典的适用场景是数组元素全为正数。比如力扣 209 题“长度最小的子数组”nums 全是正整数窗口向右扩张时和会单调递增所以当窗口内的和已经超过目标值时左指针右移缩小窗口窗口和一定减小这种单调性保证了双指针的正确性。但本题的nums允许负数。一旦有负数窗口向右扩张时和可能会变小左指针右移时和也可能会变大。单调性被打破双指针就失效了。举个例子nums [1, -1, 0], k 0如果尝试用滑动窗口你会发现很难决定什么时候收缩窗口。这也解释了为什么这题的正确解法需要换个角度我们需要一种不依赖数组元素正负性的统计方法前缀和加哈希表就是为此设计的。2. 前缀和把“区间求和”变成“两个数的差”2.1 前缀和数组的定义与推导前缀和的定义很简单定义prefix[i]表示数组nums从下标0到下标i的所有元素之和。为了处理方便通常会额外增加一个prefix[0] 0表示空数组的前缀和。于是prefix[0] 0 prefix[1] nums[0] prefix[2] nums[0] nums[1] ... prefix[i] nums[0] nums[1] ... nums[i-1]注意我这里用的是prefix[i]表示前 i 个元素的和也就是说prefix数组的长度是n 1而不是n。这样做的好处是子数组nums[i..j]的和可以直接写成sum(i, j) prefix[j 1] - prefix[i]为什么是j 1因为prefix[j 1]包含的是nums[0]到nums[j]这j 1个元素的和减去prefix[i]包含的nums[0]到nums[i - 1]这i个元素的和剩下的正好是nums[i]到nums[j]。你可以把前缀和理解成一组“里程碑”要算任意两个里程碑之间的距离只需要把两个里程碑的数值相减就行不需要回头一步一步重新走一遍。这就是前缀和能加速的核心原理。2.2 前缀和暴力枚举的改进效果如果只使用前缀和数组不配合哈希表代码可以这样写int subarraySum(vectorint nums, int k) { int n nums.size(); vectorint prefix(n 1, 0); for (int i 0; i n; i) { prefix[i 1] prefix[i] nums[i]; } int count 0; for (int i 0; i n; i) { for (int j i; j n; j) { if (prefix[j 1] - prefix[i] k) { count; } } } return count; }相比最原始的O(n³)这个版本已经快了不少但仍然是O(n²)没法通过大数据量的测试用例。真正的质变来自下一步能不能不枚举所有区间而是用一个哈希表把历史信息存下来做到只遍历一次数组就得出答案2.3 前缀和数组的边界设计在进入哈希表方案之前我提醒一下边界设计。上面我采用的是prefix[0] 0prefix[i]表示前i个元素的和。网上也有代码写成prefix[0] nums[0]prefix[i]表示nums[0..i]的和。两种写法本质等价但我在写代码时更推荐“前 i 个元素”这种原因有二空数组的前缀和是 0这样prefix[0]可以天然参与运算不需要额外讨论i 0的边界情况。子数组区间的公式sum(i, j) prefix[j 1] - prefix[i]非常统一左右端点不需要加一减一出错率更低。3. 哈希表优化把 O(n²) 压到 O(n) 的关键3.1 等式的变形是突破口暴力求解的核心问题是我需要枚举所有(i, j)组合然后判断sum(i, j) k。如果用前缀和表示这个条件变成prefix[j 1] - prefix[i] k把这个式子移项就得到了一个非常关键的变形prefix[i] prefix[j 1] - k这个式子是什么意思它的意思是当我在枚举右端点j的时候我真正关心的是——在当前位置之前有多少个前缀和的值等于prefix[j 1] - k。有多少个这样的前缀和就说明有多少个左端点i能使得nums[i..j]的和等于k。于是我不需要再枚举左端点只需要在遍历数组的过程中用一个哈希表记录每个前缀和出现的次数。每计算出一个新的前缀和current我就去哈希表里查current - k出现了多少次把次数累加到结果里。然后把这个current的次数加一继续往后走。一句话总结这个思路我在每个位置只关心“从我之前某个位置到我当前位置有没有和为 k 的子数组”而哈希表告诉我答案。3.2 核心代码实现C / Python先看 C 版本class Solution { public: int subarraySum(vectorint nums, int k) { unordered_mapint, int prefixCount; prefixCount[0] 1; // 空前缀和为 0出现 1 次 int sum 0; int count 0; for (int num : nums) { sum num; // 查一下有多少个前缀和等于 sum - k if (prefixCount.count(sum - k)) { count prefixCount[sum - k]; } // 当前前缀和存入哈希表 prefixCount[sum]; } return count; } };再看 Python 版本class Solution: def subarraySum(self, nums: List[int], k: int) - int: prefix_count {0: 1} total 0 count 0 for num in nums: total num count prefix_count.get(total - k, 0) prefix_count[total] prefix_count.get(total, 0) 1 return count整个算法的时间复杂度是O(n)空间复杂度也是O(n)因为哈希表最多存n 1个不同的前缀和。代码看起来很短但短代码往往藏了很多细节。下面我把几个关键点掰开揉碎讲清楚。3.3 为什么初始化 m[0] 1这是新手最容易卡住的一行。很多人会问“我还没开始遍历数组呢为什么哈希表里要先放一个 0 进去”原因很简单前缀和为 0 的情况在最开始时已经出现了一次那就是“空数组”。空数组的和是 0这是一个合法的“历史前缀”。举个例子nums [3], k 3。遍历到第一个元素 3 时sum 3我需要查sum - k 3 - 3 0出现在哈希表中的次数。如果不在哈希表里预先放{0: 1}这里查到的是 0那么答案就漏掉了[3]这个子数组。换句话说这个{0: 1}代表的是“下标 -1 之前的位置”即从不包括任何元素时的状态。每个合法子数组的和都是从它左端点之前的前缀和到这个位置的前缀和之差所以左端点之前可能什么都没有对应的前缀和就是 0。3.4 先查表还是先更新顺序为什么不能乱代码里的顺序是累加sum查哈希表累加结果把sum插入哈希表这个顺序为什么不能颠倒因为我要统计的子数组长度至少是 1。如果我先把当前sum插入哈希表然后查sum - k当k 0时会发生什么// 错误的顺序 sum num; prefixCount[sum]; // 先插入 count prefixCount[sum - k]; // 再查询当k 0时sum - k sum先插入再查询结果就是sum出现的次数包含了刚插入的这一次也就是把长度为 0 的空子数组也统计进去了。题目要求的是子数组长度不能为 0所以这个多余统计必须避免。正确的顺序是先查旧数据再插入新数据保证当前累积的前缀和不会影响同一轮查询。我再说一个进阶理解这一行顺序其实还决定了我们统计的“左端点”必须是“右端点之前的某个位置”不能等于右端点本身。因为子数组的长度至少为 1左端点最多到j此时子数组只有一个元素nums[j]但左端点之前的那个“前缀端点”最多到j - 1所以当前这个前缀和不能作为自己的左端点前缀。4. 常见错误与排查细节4.1 int 溢出prefix[i]的累加可能会超出int的范围。比如数组长度是10^5每个元素值可以达到10^4那么前缀和最大可以达到10^9这个还在int范围内。但如果题目把数值范围调大或者某些变态用例叠加int很容易溢出。我在写 C 代码时习惯把sum和哈希表的 key 类型直接定义成long long或long避免在边界用例上翻车。虽然力扣这道题的原始数据范围用int也问题不大但这是一个好的防御性编程习惯。unordered_maplong long, int prefixCount; long long sum 0;这样即使nums[i]是很大的整数也不会发生未定义行为。4.2 负数与零值造成的问题前缀和允许负数也允许重复出现。比如nums [1, -1, 0, 0]这个数组的前缀和依次是1, 0, 0, 0其中 0 出现了多次。哈希表的 value 存的是“次数”而不是“位置”这很关键。为什么要存次数因为同一个前缀和可能对应多个不同的左端点每一个都代表一个合法的子数组起点。比如prefix sum 0出现了三次就意味着存在三个不同的起点能形成和为目标值的子数组。负数还会导致另一个问题前缀和不单调所以不能在前缀和数组上做二分查找也不能用双指针。你必须依赖哈希表这种支持随机查询的结构。4.3 对 map 与 unordered_map 的选择C 里map和unordered_map都能存键值对但底层实现不同map基于红黑树插入和查询是O(log n)key 会按顺序排列。unordered_map基于哈希表插入和查询平均是O(1)key 无序。本题需要的是快速查询是否存在某个 key而不是按顺序遍历所以unordered_map是更合适的选择。用map虽然也能通过但在大数据量下会慢不少。Python 则统一用字典dict底层就是哈希表没有这个问题。JavaScript 的Map或普通对象也可以但需要注意Map和普通对象的 key 处理差异比如对象会把 key 转成字符串。4.4 空数组和边界条件如果nums为空数组我们的代码会直接返回 0因为循环体不会执行。这个行为是正确的不需要额外处理。如果k 0代码依然能正确运行靠的就是“先查后插”的顺序。例如nums [1, -1], k 0遍历到 1sum 1查1 - 0 1哈希表里没有count 0插入{1: 1}。遍历到 -1sum 0查0 - 0 0哈希表里有{0: 1}count 1插入{0: 2}。答案 1 是正确的只有一个子数组[1, -1]和为 0不会把空数组统计进去。4.5 常见问题速查表问题现象可能原因解决方法答案比预期多k 0且先插入后查询改为先查后插答案比预期少没有初始化prefixCount[0] 1在循环前加入{0: 1}大用例运行超时map替代了unordered_map或仍然是 O(n²)使用哈希表确保单次遍历累加和溢出int不够用改用long long子数组包含数组外的位置前缀和定义混乱统一使用“前 i 个元素”的定义这个表是我在实际刷题和帮别人 review 代码时总结出来的基本上把这几个问题检查一遍代码就能稳过。5. 举一反三同套路题目的迁移5.1 力扣 525 连续数组这道题给定一个二进制数组要求找到含有相同数量的 0 和 1 的最长连续子数组。解法是把 0 当成 -1问题就转化为“和为 0 的最长子数组”这就变成了 560 的变体只是从计数变成求最长长度。哈希表里要存的就不只是次数了而是某个前缀和第一次出现的位置。每遇到一个前缀和sum如果之前出现过相同的sum那么从第一次出现的位置到当前位置的子数组和为 0更新最大长度。这个思路就是 560 的“查历史前缀”思想的迁移。5.2 力扣 974 和可被 K 整除的子数组这道题要求统计和为K的倍数可被 K 整除的子数组个数。核心转化是把前缀和对K取模问题变成“前缀和模 K 相同的两个位置之间子数组和能被 K 整除”。需要注意负数取模的语言差异C 中负数取模可能得到负数需要统一转为非负余数比如((sum % K) K) % K。这个细节能帮你避开很多“本地跑得通提交就错”的诡异问题。5.3 力扣 437 路径总和 III树上版本的和为 K 子数组问题。二叉树中的任意一条自上而下的路径统计路径和等于目标值的路径条数。解法就是在 DFS 过程中维护前缀和路径配合哈希表回溯撤销。根节点到当前节点的路径和减去目标值如果这个值在哈希表里出现过说明存在某段路径和为 K。这个题几乎是 560 的直接移植只是线性遍历变成了树的 DFS。你可以发现“前缀和 哈希表”这个组合非常通用数组、二进制、取模、树上路径全都适用。5.4 怎么识别“前缀和哈希表”这一类题我自己的经验是当你看到以下特征时优先考虑前缀和加哈希表题目要求统计连续子数组的个数或求最长/最短连续子数组的长度。数组元素可能为负数导致双指针滑动窗口不适用。目标条件可以通过前缀和的差来等价表达比如sum(i, j) k等价于prefix[i] prefix[j 1] - k。需要在一次遍历中快速查询历史信息而不关心具体位置时存次数关心第一次位置时存下标。6. 我的刷题心得与建议6.1 这类题目在面试中的考察点“和为 K 的子数组”是力扣热题 100 中的常客面试中也经常出现。面试官让你做这题通常不是考察你知不知道标准答案而是考察三个能力第一能不能分析暴力解法的瓶颈并主动提出优化方向。很多候选人上来就写哈希表问为什么用前缀和却说不太清这其实是最容易被追问的点。第二能不能说清楚prefixCount[0] 1的含义。这行代码是这道题的灵魂能讲明白它的含义说明你真的理解前缀和和空数组之间的关系。第三能不能指出为什么不能滑动窗口。如果候选人能主动说“因为数组有负数破坏了窗口和的单调性”面试官基本会放心。6.2 刷题时的个人步骤我刷这道题和类似题目时会遵循一个固定流程先把示例在纸上手动跑一遍暴力解搞清楚答案是怎么来的。再把暴力解写成代码提交一次看看哪里超时加深对性能瓶颈的感知。然后用前缀和改写再提交一次观察复杂度下降但仍然不理想的感觉。最后才上哈希表一次通过。这个过程虽然多花时间但每次都能让我记住这个思路的推导过程。时间是花在刀刃上的比直接背答案要扎实得多。这道题的代码很短短到可能十几行就写完了但背后的推导链非常长暴力枚举到前缀和到哈希表优化每一步都建立在上一步的痛点之上。如果你能完整复述这条链以后遇到类似问题就不需要死记硬背而是能从“问题本身需要什么”出发自己推出解法。