企业官网建设流程全解析

如果你正在刷算法题，或者准备蓝桥杯、天梯赛这类比赛，前缀和这个概念是怎么都绕不过去的。而一提到前缀和，有两道题几乎总是连着出现：和为 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(vector<int>& nums, int k) { unordered_map<int, 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。如果哈希表初始为空，遍历过程是这样的：

• i=0，cur=2，查询 mp[-1] = 0，更新 mp[2] = 1；
• i=1，cur=5，查询 mp[2] = 1，ans=1，更新 mp[5]。

看上去好像也能得到 1，但这是运气好。再看nums = [3]，k = 3。如果初始为空：

• i=0，cur=3，查询 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(vector<int>& nums, int k) { unordered_map<int, 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*(n+1)/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 一张表看懂两道题的查表差异

我平时带人的时候，最常画的就是下面这张对比表，看一遍就能把两道题的区别记牢：

看到没有，初始化这一行两道题都是一样的，都必须有。原因之前说过：前缀和从空数组开始的那个 0，是所有从头计起的子数组的边界。少了它，计数就会漏掉一批情况。

4.3 记忆锚点与口算训练

很多同学刷了这道题，隔两周又忘了。我的建议是不要背代码，背三句话就行：

• 第一句：区间和等于两个前缀和的差。
• 第二句：等于 k 就查差值，能被 k 整除就查余数。
• 第三句：边算前缀和边查，查完再入哈希表。

这三句话能现场推演出完整代码。另外建议你练一下口算前缀和：随便给一个数组，在心里快速写出前缀和序列，再写出取模序列。这个能力在面试的时候特别有用，因为面试官很可能要求你当场跑一个例子验证代码，如果你能快速口算出前缀和序列，心里会非常有底。

5. 常见问题与排查技巧实录

5.1 新手最容易犯的四个错

我把这些年看到的高频错误汇总成一张排查表，你自己对照检查：

第一行是漏初始化，第二行是查询顺序，第三行是负数取模，第四行是溢出。这四个问题基本覆盖了这两道题 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 和 k=3 这种能体现关键逻辑的用例。跑的时候重点说明：为什么初始化cnt[0] = 1，为什么查询在更新之前，取模修正那行是怎么来的。

竞赛场景里时间紧，代码要写得保守一点，前缀和能用long long就用long long，哈希表能用数组映射就尽量用数组映射，减少不必要的动态哈希开销。如果你确定前缀和的范围不大，比如所有元素绝对值之和不超过几百万，也可以用数组当哈希表来加速，而不一定非用unordered_map。

我在实际带学员的过程中发现，这两道题放在一起刷的效果是最好的。先做“和为 k”，再做“和可被 k 整除”，不会觉得跨度很大，因为整个框架是共通的，只不过第二道题多了一个“取模修正”的坎。最后再分享一个小习惯：我每次讲完这两道题，都会让学员自己再造一个变形题，比如“和为 k 的倍数的子数组有多少个”，然后按这套模板重新推一遍。能把新题看着不像原题、但最后发现用的还是同一套前缀和加哈希表，那才是真正把这类题吃透了。