如果你正在刷算法题或者准备蓝桥杯、天梯赛这类比赛前缀和这个概念是怎么都绕不过去的。而一提到前缀和有两道题几乎总是连着出现和为 k 的子数组、和可被 k 整除的子数组。这两道题表面上看一个在搞定“等于某个数”的问题另一个在搞定“能不能被某个数整除”的问题实际上共用同一套“前缀和加哈希表”的底层套路。但它们中间的细节差异尤其是负数取模、初始化时机、查询顺序这几个坎做得不到位就容易全盘皆错。这篇文章我想把自己反复给学员讲的那套推导过程、代码模板以及自己踩过的坑完整写出来。适合刚接触前缀和的新手也适合准备算法面试想快速过一遍套路的人。读完你不仅能对付这两道题还能顺手把一堆“连续子数组统计”类型的题目打通。1. 前缀和到底是什么为什么子数组问题都爱用它1.1 从暴力枚举到前缀和的思维跳跃先回到最原始的问题给你一个数组让你求某个连续子数组的和你会怎么做最笨的办法是枚举起点 i 和终点 j然后依次累加复杂度是 O(n³)。稍微优化一点先用一个循环算出每个位置的前缀和再用减法求区间和枚举所有区间仍然是 O(n²)。但很多题目数据范围一给到 10⁵ 甚至 10⁶O(n²) 直接超时。这时候前缀和的价值就出来了它把“区间求和”这个动作从 O(区间长度) 压缩到 O(1)。什么是前缀和简单来说pre[i]表示数组前 i 个元素的和。用信奥里最常见的写法假设数组下标从 1 开始pre[0] 0 pre[i] pre[i - 1] a[i]那么任意区间[l, r]的和就是sum pre[r] - pre[l - 1]这套公式看着简单但它才是整道题的灵魂。你再往后看会发现几乎所有子数组求和类问题最终都是在“两个前缀和之间做文章”而不是真的去循环求和。1.2 两道题如何变成“查哈希表”的问题回头看我们手上的两道题。第一道和为 k 的子数组。它要求的是“存在多少个区间 [i, j]使得区间和等于 k”。用前缀和表达就是pre[j 1] - pre[i] k第二道和可被 k 整除的子数组。它要求的是“存在多少个区间 [i, j]使得区间和能够被 k 整除”。用前缀和表达就是(pre[j 1] - pre[i]) % k 0看到没有两个问题都在描述“两个前缀和之间的关系”。暴力做法会去枚举所有 i 和 j那就是 O(n²)。而我们希望只用一遍遍历就完成统计这就必须引入哈希表。第一道等价于“找两个前缀和它们的差是 k”。第二道等价于“找两个前缀和它们对 k 取模的余数相同”。这就是哈希表能发挥作用的地方——你遍历的过程中把已经见过的前缀和或者余数记录下来后面的位置只需要查表就知道前面有多少个位置能和它配对。这个思维转换就是两道题的核心。前面先建立一个整体印象下面我就把两道题分别拆开每一步推导都写清楚。2. 第一道题和为 k 的子数组核心公式推导与代码实现2.1 把区间求和问题改写成“找两数之差等于 k”题目给你一个数组nums和一个整数k让你统计有多少个连续子数组的和正好等于k。先明确一点子数组必须是连续的而且不能为空。我习惯用前缀和数组做一个等价变换。设cur是当前遍历到的前缀和也就是pre[j 1]。如果存在某个之前的pre[i]使得cur - pre[i] k那么说明区间[i, j]的和就是k。把这个式子换个写法pre[i] cur - k这就变成了一个问题在当前这个位置我要知道之前已经出现过多少个pre[i]它们的值正好等于cur - k。这个信息用哈希表来存就非常自然Key 是前缀和的值Value 是这个值出现的次数。为什么非要转化成“两个前缀和之差”因为如果直接去枚举起点每个终点就要试遍所有起点那必然是 O(n²)。转化之后每个终点只需要 O(1) 查一次哈希表整体就是 O(n)。2.2 一步一步走查一个例子光看公式容易晕我拿一个最常见的例子走一遍nums [1, 1, 1]k 2。手动算一下答案应该是 2因为子数组[0, 1]的和是 2[1, 2]的和也是 2。用哈希表统计的过程是这样的。先把mp[0] 1放进去这一步是为了处理从数组开头就满足条件的子数组后面我会单独说为什么必须这么做。初始: mp {0: 1} cur 0 遍历 nums: i 0, x 1 cur 0 1 1 查询 mp[cur - k] mp[-1] 0 更新 mp[1] 1 当前 mp {0: 1, 1: 1} i 1, x 1 cur 1 1 2 查询 mp[cur - k] mp[0] 1 更新 mp[2] 1 当前 mp {0: 1, 1: 1, 2: 1} i 2, x 1 cur 2 1 3 查询 mp[cur - k] mp[1] 1 更新 mp[3] 1两次查询都命中了答案就是 2。每次命中一个mp[cur - k]的值就说明“以当前位置为终点”的合法子数组新增了这么多。比如第二次查询命中mp[0] 1此时cur 2说明之前有一个前缀和等于 0那pre[当前] - pre[那个位置] 2 - 0 2正好对应区间[0, 1]。第三次查询命中mp[1] 1说明之前有一个前缀和等于 1那pre[当前] - pre[那个位置] 3 - 1 2正好对应区间[1, 2]。这个走查过程值得多看两遍。你会发现每次查询到的计数并不是“找到了一个子数组”而是“找到了以当前终点为结尾的若干个子数组”。因为之前可能出现多个相同的前缀和每一个都能和当前形成合法区间。2.3 完整代码与“先查后更新”的纪律直接上 C 版本这是面试里最常写的版本class Solution { public: int subarraySum(vectorint nums, int k) { unordered_mapint, int mp; mp[0] 1; int cur 0; int ans 0; for (int x : nums) { cur x; ans mp[cur - k]; mp[cur]; } return ans; } };Python 版本也很短def subarray_sum(nums, k): from collections import defaultdict cnt defaultdict(int) cnt[0] 1 cur ans 0 for x in nums: cur x ans cnt[cur - k] cnt[cur] 1 return ans代码里有一个极其重要的顺序一定要先ans mp[cur - k]再mp[cur]。我见过很多人在这个地方翻车把顺序写反先把自己的cur加进哈希表然后才查询。如果k 0那么cur - k cur你查询到的mp[cur]就包含了刚放进去的当前前缀和本身相当于把一个长度为零的“空子数组”也算进去了答案就会虚高。即使k不等于 0先更新后查询的习惯也可能在后续扩展题目里埋雷。2.4 为什么初始化哈希表要放一个 mp[0] 1再看一个容易忽略的点mp[0] 1这一行绝大多数情况下不能省。为什么因为我们要统计的pre[i]i 的范围是从 0 到 n-1 的也就是前缀和可以取到“一个元素都没取”的状态。举个例子nums [2, 3]k 3。合法的子数组是[3]答案应该是 1。如果哈希表初始为空遍历过程是这样的i0cur2查询 mp[-1] 0更新 mp[2] 1i1cur5查询 mp[2] 1ans1更新 mp[5]。看上去好像也能得到 1但这是运气好。再看nums [3]k 3。如果初始为空i0cur3查询 mp[0] 0答案是 0。但实际上[3]本身就满足条件。为什么没查到因为从头开始的子数组对应的pre[i]是pre[0] 0而 0 这个前缀和从一开始就应该存在于哈希表中。初始化mp[0] 1就是把这个“空前缀”提前放进去表示在数组开始之前存在一个前缀和等于 0。这一行对整个算法的正确性起着决定性作用。3. 第二道题和可被 k 整除的子数组负数取模是最大的坑3.1 同余条件改写哈希表从“存前缀和”变成“存余数”第二道题要求统计有多少个子数组的和可以被 k 整除。设区间[i, j]的和为sum条件就是sum % k 0用前缀和表示(sum of [i, j]) % k 0 (pre[j 1] - pre[i]) % k 0 pre[j 1] % k pre[i] % k最后一步其实用到了模运算的性质如果两个数相减能被 k 整除那这两个数对 k 取模的结果必然相等。反过来也成立。所以问题就转化成了遍历过程中统计“之前有多少个前缀和对 k 取模后的余数和当前前缀和一样”。这就是第一道题和第二道题的根本区别第一道题的哈希表里存的是前缀和本身第二道题的哈希表里存的是前缀和对 k 取模后的余数。理解了这个区别你就能记住两套代码的差异在哪里。3.2 C、Java 负数取模的坑与数学补正这一部分是最容易踩坑的地方也是很多人对着正确答案百思不得其解的根源。C 和 Java 里%运算的结果符号和被除数一致。比如-5 % 3结果不是 1而是 -2。因为 C 的取模运算遵循的是“商向零取整”-5 / 3 -1因为 -1 是向零取整的结果余数 -5 - (-1 * 3) -2。但在数学意义上-5 除以 3余数应该是 1因为 -5 -2 * 3 1。Python 的%规则不同它会保证余数非负-5 % 3的结果是 1。这就导致一个严重的问题如果直接拿负的cur去取模C 里得到的余数可能是负数而负数和正数永远不相等明明余数相同的两个前缀和就被错误地“拆开”了。解决办法是加一次修正把所有负数余数平移到非负区间int r (cur % k k) % k;解释一下这个式子的含义cur % k可能是负数加上一个 k 之后如果它原本是负数就会变成一个 0 到 k-1 之间的正数如果它原本是正数加上 k 会超过 k所以再取一次模把它压回来。这是所有 C/Java 写法里必须做的动作千万别偷懒省略。3.3 完整代码与走查同一个余数出现多次的含义给出 C 完整代码class Solution { public: int subarraysDivByK(vectorint nums, int k) { unordered_mapint, int cnt; cnt[0] 1; int cur 0; int ans 0; for (int x : nums) { cur x; int r (cur % k k) % k; ans cnt[r]; cnt[r]; } return ans; } };Python 里可以少写一层修正因为 Python 的取模结果天然非负def subarrays_div_by_k(nums, k): from collections import defaultdict cnt defaultdict(int) cnt[0] 1 cur ans 0 for x in nums: cur x r cur % k ans cnt[r] cnt[r] 1 return ans用一个简单例子看会很清楚nums [1, 2, 3]k 3。所有合法子数组是[1, 2]、[3]、[1, 2, 3]一共 3 个。前缀和序列是 1、3、6取模余数是 1、0、0。走查过程初始: cnt {0: 1} i 0, cur 1, r 1 查询 cnt[1] 0 更新 cnt[1] 1 i 1, cur 3, r 0 查询 cnt[0] 1 更新 cnt[0] 2 i 2, cur 6, r 0 查询 cnt[0] 2 更新 cnt[0] 3第一次查询cnt[0] 1命中对应pre[2] - pre[0] 3也就是子数组[1, 2]。第二次查询cnt[0] 2命中了两个位置一个是空前缀pre[0] 0对应子数组[1, 2, 3]另一个是pre[2] 3对应子数组[3]。所以余数计数为 2答案就加上 2。这一下就能理解为什么“同一个余数出现多少次就能组成多少个合法子数组了”。3.4 边界情况k 为 1、数组全为 0 或全为负数时怎么办有些边界情况值得单独拿出来说因为它们很容易让初学者怀疑代码写错了。先看 k 1。任何整数对 1 取模都是 0也就是说任意一个子数组的和都能被 1 整除。如果你的代码在nums [1, 2, 3]k 1 时输出的不是 6那一定有问题。验证方法也很简单直接按子数组个数公式算长度为 3 的数组子数组总数是 n*(n1)/2 6答案应该是 6。再看数组全为 0 的情况比如nums [0, 0, 0]k 2。每个子数组的和都是 0都能被 2 整除所以答案也是 6。这个用例拿来测初始化是否缺失特别好使。最后是全负数的情况比如nums [-1, -2, -3]k 3。合法子数组有[-1, -2]和 -3、[-3]和 -3、[-1, -2, -3]和 -6答案 3。这种用例能实际检验你 C 里有没有写(cur % k k) % k这个修正如果没写匹配会乱掉。4. 两道题合并记忆套路拆解与变形方向4.1 同一套模板的三种改法把两道题放在一起看你会发现一个非常稳定的“三板斧”套路。遇到任何“连续子数组 求和 统计个数”的题目先别急着写暴力按这个顺序走第一步写出前缀和的更新代码cur x这个公式在信奥里写烂了但每次都要保持清醒。第二步把题目的语言翻译成前缀和之间的关系。“等于 k”翻译成差值关系“能被 k 整除”翻译成余数关系。第三步用哈希表做边遍历边统计查询当前cur需要匹配的目标再把当前cur写入哈希表。这套模板还可以继续泛化。比如“和为 k 的最长子数组长度”代码结构几乎一模一样只是哈希表里存的不是次数而是某个前缀和第一次出现的位置查询命中时用当前位置减去第一次出现位置更新答案时只取最大值。再比如“前缀和数组中找最接近某个值的子数组”可能就需要前缀和加二分或者平衡树。但核心仍然是先写出前缀和再去想两个前缀和之间满足什么关系。4.2 一张表看懂两道题的查表差异我平时带人的时候最常画的就是下面这张对比表看一遍就能把两道题的区别记牢对比项和为 k 的子数组和可被 k 整除的子数组核心公式pre[j1] - pre[i] k(pre[j1] - pre[i]) % k 0等价条件找前缀和值等于 cur - k找余数等于 (cur % k)哈希表 Key前缀和本身前缀和对 k 取模的余数查询内容cnt[cur - k]cnt[(cur % k k) % k]负数处理不需要特殊处理C/Java 必须做负数修正初始化cnt[0] 1cnt[0] 1看到没有初始化这一行两道题都是一样的都必须有。原因之前说过前缀和从空数组开始的那个 0是所有从头计起的子数组的边界。少了它计数就会漏掉一批情况。4.3 记忆锚点与口算训练很多同学刷了这道题隔两周又忘了。我的建议是不要背代码背三句话就行第一句区间和等于两个前缀和的差。第二句等于 k 就查差值能被 k 整除就查余数。第三句边算前缀和边查查完再入哈希表。这三句话能现场推演出完整代码。另外建议你练一下口算前缀和随便给一个数组在心里快速写出前缀和序列再写出取模序列。这个能力在面试的时候特别有用因为面试官很可能要求你当场跑一个例子验证代码如果你能快速口算出前缀和序列心里会非常有底。5. 常见问题与排查技巧实录5.1 新手最容易犯的四个错我把这些年看到的高频错误汇总成一张排查表你自己对照检查错误现象原因修复方法答案少算尤其少了从开头开始的子数组忘记初始化cnt[0] 1最开始加一行cnt[0] 1k 0 时答案明显偏大先更新哈希表再查询把空子数组算进去了改成先查询、后更新负数数据跑出来答案完全不对C 取模结果是负数用(cur % k k) % k修正大数组接近边界时答案异常前缀和累加超出 int 范围前缀和和计数变量都用long long第一行是漏初始化第二行是查询顺序第三行是负数取模第四行是溢出。这四个问题基本覆盖了这两道题 90% 的报错场景不信你去看 LeetCode 对应题目的评论区翻来覆去都是这些问题。5.2 用暴力对拍快速定位代码问题遇到代码结果不对不要在脑子里硬想最快的方式是对拍。你先写一个最笨、最不可能错的暴力版本枚举所有子数组求和算答案然后拿随机小数据跟你的前缀和版本跑对比一旦结果不一致立刻缩小范围。一个最简单的 Python 对拍脚本思路是这样的随机生成一个长度为 5 到 10 的数组随机生成一个 k分别跑暴力版和前缀和版对比输出只要不一致就把这组数据单独打出来人工走查。这个方法的效率远高于肉眼盯代码。我自己的习惯是不管题目多简单提交之前都会在本地跑几个特殊用例一定包括全正数、全负数、包含 0 的数组、k 等于 1、k 等于数组长度这种极端值。这些用例能同时验证初始化和取模修正两个问题。5.3 面试和竞赛里的表述建议这两道题在算法面试里出现频率很高答题的时候建议按这个顺序来面试官一眼就知道你会不会先主动报复杂度告诉大家暴力的做法是 O(n²)因为要枚举所有起点和终点。然后说优化思路利用前缀和把区间和变成 O(1)再用哈希表把匹配降到 O(1)整体 O(n)。接着写代码写完后自己挑一个例子跑一遍比如 1 2 3 和 k3 这种能体现关键逻辑的用例。跑的时候重点说明为什么初始化cnt[0] 1为什么查询在更新之前取模修正那行是怎么来的。竞赛场景里时间紧代码要写得保守一点前缀和能用long long就用long long哈希表能用数组映射就尽量用数组映射减少不必要的动态哈希开销。如果你确定前缀和的范围不大比如所有元素绝对值之和不超过几百万也可以用数组当哈希表来加速而不一定非用unordered_map。我在实际带学员的过程中发现这两道题放在一起刷的效果是最好的。先做“和为 k”再做“和可被 k 整除”不会觉得跨度很大因为整个框架是共通的只不过第二道题多了一个“取模修正”的坎。最后再分享一个小习惯我每次讲完这两道题都会让学员自己再造一个变形题比如“和为 k 的倍数的子数组有多少个”然后按这套模板重新推一遍。能把新题看着不像原题、但最后发现用的还是同一套前缀和加哈希表那才是真正把这类题吃透了。