企业官网建设流程全解析

做了七年算法教学，最常被问到的就是"前缀和到底在解决什么问题"。这个疑问一般来自 LeetCode 560 和 974 这两道题——一道是"和为 k 的子数组"，另一道是"和可被 k 整除的子数组"。这两题看着差不多，但暗坑完全不一样。这篇文章我把两题的推导过程、完整代码、负数取模的坑、面试表述技巧全写清楚，适合正在刷题准备面试的开发者，也适合信奥、蓝桥杯方向刚接触前缀和的同学。跟着走一遍，你会发现这类"子数组计数"题型其实就是一套固定模板。

1. 从"和为k的子数组"起手：暴力枚举为什么注定被淘汰

1.1 先搞清楚题目到底在问什么

第 560 题的描述很简洁：给你一个整数数组nums和一个整数k，请统计并返回该数组中和为k的连续子数组的个数。

注意两个关键词。第一个是"连续"，意味着子数组必须是在原数组中紧挨着的一段，不能随意挑元素组合，这排除了类似"子集"的玩法。第二个是"个数"，不是让你输出具体是哪几个区间，只需要返回数量，这个条件决定了后面可以用哈希表只计次数而不存区间索引。

光说概念容易飘，举两个具体例子。

• nums = [1,1,1], k = 2：连续子数组有[1,1]、[1,1]（分别从下标0和下标1开始），一共2个。
• nums = [1,2,3], k = 3：[1,2]和[3]都满足，共2个。
• nums = [-1,-1,1], k = 0：连续子数组[-1,1]满足，共1个。

第三组例子特意带了负数和k=0，因为后面你会发现k=0的情况最容易把初学者坑进"计数重复"的陷阱里。

1.2 暴力解法的复杂度到底有多可怕

很多人第一反应是枚举所有可能的左边界i和右边界j，然后对区间[i, j]求和，判断是否等于k。

最朴素的写法是三层循环：外层枚举左边界，内层枚举右边界，最内层从i加到j求和，复杂度O(n^3)。稍微有点经验的人会先预处理一个前缀和数组，把"求区间和"从O(n)降到O(1)，这样仍然是两层循环枚举所有区间，复杂度降到O(n^2)。

你以为O(n^2)就安全了？看数据范围。560 题1 <= nums.length <= 2 * 10^4，也就是n = 20000。n^2 = 4 * 10^8，接近四亿次基本操作。普通判题机一秒通常只能跑10^7~10^8量级的简单运算，四亿次循环外加哈希表查询、边界判断，实际耗时大概率在几秒甚至十几秒，TLE 几乎是必然的。

这就是为什么要寻找低于O(n^2)的方案。O(n log n)可以接受，O(n)是理想情况。而前缀和正是把这类问题从平方级拉到线性级的核心工具。

1.3 前缀和最核心的一句话：区间和=两个前缀和的差

定义前缀和数组pre，其中pre[i]表示原数组nums[0]到nums[i-1]的和。换句话说，pre[i]是"前 i 个元素的总和"。

pre[0] = 0 pre[1] = nums[0] pre[2] = nums[0] + nums[1] pre[3] = nums[0] + nums[1] + nums[2] ...

为什么要这样定义？因为任意连续子数组nums[j]到nums[i-1]的和，可以表示为：

sum[j, i) = pre[i] - pre[j]

这个公式是整个前缀和专题的地基。打个比方，你记了一本账，pre[i]是截止到第i天的累计花费，那么"从第j+1天到第i天"花了多少钱，就是pre[i]减去pre[j]的差额；中间那段时间具体怎么花的，你根本不用关心。

有了这个公式，560 题就变成了一道纯粹的数学题：找有多少对(j, i)，满足j < i且pre[i] - pre[j] = k。

2. 核心推导：前缀和加哈希表，一次遍历拿下"和为k的子数组"

2.1 把"区间和等于k"改写成"两数之差等于k"

上面已经把问题转化成了对(j, i)的计数问题：

pre[i] - pre[j] == k (j < i)

稍微变形一下：

pre[j] == pre[i] - k

这个变形式子是整个解法的钥匙。它意味着：当我站在某个位置i，手里拿着当前的前缀和cur = pre[i]，我只需要关心"在这之前，出现过多少个前缀和的值恰好等于cur - k"。有多少个，就有多少个以i为右端点且和为k的子数组。

为什么要强调"在这之前"？因为j必须小于i，子数组才能是空区间以外的合法区间。如果把自己也算进去，当k=0时就会出现明显的虚增。

2.2 用哈希表记录"前缀和值"出现次数

既然题目只要求统计个数，不需要回传具体区间，那么哈希表的键可以设为"前缀和的值"，值设为"该前缀和已经出现的次数"。

扫描数组时维护一个计数器逻辑：

1. 累加当前前缀和cur；
2. 查询哈希表中cur - k的出现次数，把结果加入答案；
3. 把当前cur的出现次数加 1，更新哈希表。

关键点在于第二步和第三步的先后顺序。必须先查询、后更新，确保只用之前的"旧"前缀和来配对，不会把当前这个前缀和本身当作j使用。

cnt[0] = 1这个初始化是初学者最容易被劝退的地方。它的含义是：在数组正式开始遍历之前，已经存在一个"空前缀和"，值为 0。为什么要它？因为当cur本身就等于k时，满足cur - k = 0，这意味着从左边界0到当前下标i-1这整个区间就是一个合法子数组，这个区间对应j = -1，也就是pre[-1]不存在，但它确实对应pre[0] = 0这个概念上的空前缀。不初始化cnt[0] = 1，这类子数组会被漏掉。

2.3 完整代码：C++ 和 Python 双版本

C++ 版本：

class Solution { public: int subarraySum(vector<int>& nums, int k) { unordered_map<int, int> cnt; cnt[0] = 1; // 空前缀和 int cur = 0, ans = 0; for (int x : nums) { cur += x; // 当前前缀和 pre[i] ans += cnt[cur - k]; // 有多少个旧前缀和等于 cur - k cnt[cur]++; // 当前前缀和投入使用 } return ans; } };

Python 版本：

class Solution: def subarraySum(self, nums: List[int], k: int) -> int: cnt = {0: 1} cur = 0 ans = 0 for x in nums: cur += x ans += cnt.get(cur - k, 0) cnt[cur] = cnt.get(cur, 0) + 1 return ans

注意 Python 里的cnt.get(cur - k, 0)，当cur - k这个键不存在时返回 0，不会抛 KeyError。

2.4 手动跑一个例子，看看计数器是怎么工作的

拿nums = [1,1,1], k = 2手动走一遍：

• 初始化：cnt = {0: 1}，cur = 0，ans = 0
• 处理x = 1：cur = 1，查cnt[-1] = 0，ans = 0；更新cnt[1] = 1
• 处理x = 1：cur = 2，查cnt[0] = 1，ans = 1；更新cnt[2] = 1
• 处理x = 1：cur = 3，查cnt[1] = 1，ans = 2；更新cnt[3] = 1

最后ans = 2，与预期完全一致。第一个满足条件的子数组来自j=-1对应的空前缀，第二个来自前缀和pre[1] = 1和pre[3] = 3的差值。当cur=2时查cnt[0]，命中的就是cnt[0]=1这个初始化值，这正说明了cnt[0]=1的重要性。

再试一个带负数的例子：nums = [-1, -1, 1], k = 0。

• 初始cnt = {0: 1}
• 处理-1：cur = -1，查cnt[-1] = 0，更新cnt[-1] = 1，ans = 0
• 处理-1：cur = -2，查cnt[-2] = 0，更新cnt[-2] = 1，ans = 0
• 处理1：cur = -1，查cnt[-1] = 1，ans = 1；更新cnt[-1] = 2

最终ans = 1，也就是[-1, 1]这段，正确。注意哈希表的键值完全可以是负数，C++ 的unordered_map<int, int>和 Python 的 dict 都支持负整数键。

2.5 复杂度与空间取舍分析

单次遍历数组，哈希表查询和更新都是平均O(1)，整体时间O(n)。空间上，最坏情况下前缀和的值可能每个都不同，哈希表最多存n+1个键，所以空间O(n)。

这里还有一个值得说的点：在这个问题里，哈希表只存"出现次数"就够用了，不需要存索引列表。因为题目要的是"数量"，不是要你输出具体是哪些区间。如果题目改成"找出和为 k 的最短子数组长度"或者"输出所有合法区间"，哈希表才需要升级成值 -> 索引列表的映射。这也是为什么我一再强调审题重要：同样是子数组和问题，题目诉求不同，数据结构的设计就不同。

3. "和可被k整除的子数组"：同余定理上场，负数取模才是真正的坑

3.1 题目描述：第二题比第一题多了什么

第 974 题的描述是：给定一个整数数组nums和一个整数k，返回其中和可被k整除的（连续、非空）子数组的数目。

nums的长度同样是1 <= n <= 2 * 10^4，但k的范围是1 <= k <= 10^4，注意这里的k为正整数，不存在k=0的情况。nums[i]的范围是-10^4 <= nums[i] <= 10^4，负数是一定会出现的。

相比 560 题，这里的条件从"区间和恰好等于一个数"变成了"区间和是一个数的整数倍"。如果你上来就用暴力枚举，复杂度依然爆炸。而用前缀和的思路，区间和是pre[i] - pre[j]，目标条件变成：

(pre[i] - pre[j]) % k == 0

3.2 同余定理：两个前缀和的余数相同，差值就能整除

模运算有一个基本性质：如果两个数对k取模的余数相等，那么它们的差一定能被k整除。反过来也一样成立。

用数学语言表达就是同余：

pre[i] − pre[j] ≡ 0 (mod k) 等价于 pre[i] ≡ pre[j] (mod k)

打一个直观的比方：你记录每天口袋里硬币数量的变化，如果两个时间点的余数相同，比如都是"除以5余3"，那么这两个时间点之间增加的硬币数一定可以被5整除。

所以 974 题的解法框架和 560 题几乎一致，区别只有一个：560 题哈希表的键是"前缀和的原始值"，974 题哈希表的键是"前缀和对 k 取模后的余数"。每到一个新位置，我把当前前缀和的"余数"算出来，查一下之前有多少个前缀和余数和它相同，累加进答案。

3.3 负数取模：C++ 的 % 不是数学意义上的取模

这才是 974 题真正的深水区。

在数学里，对一个整数x除以正整数k，余数的定义是x = q * k + r，其中0 <= r < k。注意这个余数必须是非负的。

但在 C++ 和 Java 里，%运算符的结果符号跟随被除数。举例：

-7 % 5 // 结果是 -2，而不是 3

为什么？因为 C++ 用的是截断除法（truncated division）：计算-7 / 5 = -1（直接舍弃小数部分），然后余数-7 - (-1 * 5) = -2。而在数学正宗的定义里，-7 = (-2) * 5 + 3，余数应该是 3。

问题是-2和3虽然"数学上同余"（差 5，能被 5 整除），但它们在 C++ 的哈希表里是两把不同的键！如果你直接用cur % k当作键，那么余数-2和3会被当成两个不同的桶，从而漏掉大量合法子数组。

修正方法很简单，统一换算成非负余数：

int mod = ((cur % k) + k) % k;

先取一次模得到范围在-(k-1)到k-1之间的数，加上k变成1到2k-1之间的正数，再取一次模，最终落到[0, k-1]。这套写法是业界标准配方，见到"取模 + 负数范围"就直接套。

这里要特别说明：Python 的%运算符本来就是数学意义上的取模，-7 % 5返回3，符合同余逻辑，不需要额外修正函数。所以一份代码在不同语言里的行为差异，恰恰是面试和笔试现场最容易翻车的地方。

3.4 完整代码：C++ 用数组当哈希表，Python 一行取模

既然余数的范围已知是[0, k-1]，一共k种可能，就没必要用unordered_map了，直接用数组更高效，还能避免哈希碰撞带来的常数恶化。C++ 版本：

class Solution { public: int subarraysDivByK(vector<int>& nums, int k) { vector<int> cnt(k, 0); cnt[0] = 1; // 空前缀和的余数为 0 int cur = 0, ans = 0; for (int x : nums) { cur += x; int mod = ((cur % k) + k) % k; // 统一成非负余数 ans += cnt[mod]; cnt[mod]++; } return ans; } };

Python 版本：

class Solution: def subarraysDivByK(self, nums: List[int], k: int) -> int: cnt = [0] * k cnt[0] = 1 cur = 0 ans = 0 for x in nums: cur += x mod = cur % k # Python 负数取模结果天然非负 ans += cnt[mod] cnt[mod] += 1 return ans

注意cnt的下标只有0到k-1，如果忘记对负数做修正，C++ 里会出现cnt[-2]这种越界访问，轻则答案错误，重则直接运行时错误。这种错误非常隐蔽，我见过不少同学自查半天才发现是取模符号问题。

3.5 跑一个官方示例验证

用官方示例nums = [4, 5, 0, -2, -3, 1], k = 5。要求答案 7。

手动走一遍关键节点：

• 初始化cnt[0] = 1，cur = 0
• 处理4：cur = 4，mod = 4，cnt[4]=0，随后cnt[4]=1
• 处理5：cur = 9，mod = 4，cnt[4]=1，ans=1；cnt[4]=2（子数组[4,5]模5为4，前缀和4和9同余）
• 处理0：cur = 9，mod = 4，cn t[4]=2，ans=3；cnt[4]=3（这里[0]、[4,5]、[4,5,0]都计入了）
• 处理-2：cur = 7，mod = 2，cnt[2]=0，随后cnt[2]=1
• 处理-3：cur = 4，mod = 4，cnt[4]=3，ans=6；cnt[4]=4
• 处理1：cur = 5，mod = 0，cnt[0]=1，ans=7；cnt[0]=2

最终 7，与题目输出一致。注意最后cur=5，mod=0时命中的是cnt[0]=1，这意味着整个数组[4,5,0,-2,-3,1]的和 5 能被 5 整除，是一个从下标 0 开始的合法子数组，再次印证了cnt[0] = 1的初始化价值。

4. 把两道题放在一起看：抽象出一个"两数之差+哈希计数"的通法

4.1 两题对比表：相似写法与致命差异

560 和 974 刷完之后，最好做一次横向对比，不然下次换一道变形题还是容易懵。

两张表看下来，会发现 974 几乎就是 560 的镜像：把"值"换成"余数"，把"差等于 k"换成"差被 k 整除"，剩下的循环结构、更新顺序、初始化方法一字不改。这就是为什么说前缀和专题是"一通百通"的题型——你掌握了其中一题的骨架，另一题只是换了件马甲。

4.2 为什么第二题在实际刷题中更常卡壳

从我在群里看到的提问频率来说，974 的平均卡壳概率明显高于 560。原因不外乎三点。

第一，取模符号问题。C++ 和 Java 的%对负数不友好，这属于语言层面的"坑"，很多人第一次见根本意识不到-2和3竟然要归入同一个桶。第二，cnt[0] = 1在两题中的含义被误读。560 里它代表"空前缀和的值为 0"，974 里它代表"空前缀和的余数为 0"，如果理解不到位，两题都会出问题。第三，有人容易把 974 误写成 560 的直接套用，用pre[i]原始值当键，忘了先取余数。其实只要记住"能被 k 整除看余数是否相同"这个同余口诀，思路就不会歪。

4.3 从两道题提炼的通用解题框架

这两题可以归纳成一套标准流程，适用于大量"连续子数组满足某个条件"的计数问题。

第一步，建立前缀和。明确声明pre[i]表示前i个元素的和，区间[j, i)的和是pre[i] - pre[j]。

第二步，改写目标条件。把题目要求翻译成关于pre[i]和pre[j]的关系式，例如pre[i] - pre[j] == k或(pre[i] - pre[j]) % k == 0。

第三步，确定哈希表的键。问自己一个问题：如果固定右端点i，我需要在历史数据里查询什么？答案就是要查的目标表达式。对于"差等于 k"，查询的是pre[i] - k；对于"差能被 k 整除"，查询的是和pre[i]同余的余数。

第四步，边遍历边统计。每更新一个cur，先查询再更新，保证只用旧数据配对，然后cur自己入表，供后面的位置使用。

这套流程可以口头表达，也可以写在草稿纸上帮助定位。遇到变形题时，先别急着写代码，花一分钟把第二步的等式写出来，思路往往就通了。

5. 前缀和的模型扩展：矩阵、树与更多子数组问题的迁移

5.1 二维前缀和：从数组到矩阵

一维前缀和解决的是一个数组上的连续段求和问题，二维前缀和则解决矩阵里的矩形区域求和问题。定义S[i][j]为从左上角(0,0)到(i,j)的所有元素之和，那么任意子矩阵(x1, y1)到(x2, y2)的和可以表示为：

S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]

这个公式用到了"容斥"思想：减掉两个多余部分，再加回重复减掉的一小块。它和"两个前缀和之差"是一回事，只是从一维的"相减"升级成二维的"加减交叠"。LeetCode 304 题就是直接把这种查询用到静态矩阵上。

如果你刷完了 560 和 974，可以去看看"矩形区域和不超过 k 的最大数值和"这类的困难题，本质上就是二维前缀和加有序集合，思路骨架还是那套"差值"逻辑。

5.2 树上前缀和：把路径问题变成差值问题

树结构也有前缀和的概念。从根节点到节点u的路径上所有节点权值之和，可以记为pre[u]。那么对于树上任意两个祖先-后代节点u和v，它们之间的路径上所有节点权值之和就是pre[v] - pre[父节点(u)]。

这和数组里的做法如出一辙：把线段上的区间和问题，迁移到树上的路径和问题。竞赛题里的"树上两点路径点权和"、"最长异或路径"都可以用这类思路处理。不过这篇不展开树的细节，先记住这个概念：前缀和不只是数组的专利，只要一个结构支持"从起点到某个位置的累计值"，差值的套路就能用。

5.3 什么时候不应该用前缀和：滑动窗口的适用边界

如果说全篇都在讲"前缀和好、前缀和万能"，那是不负责任的。有一类子数组题，用滑动窗口更优，而且空间是 O(1)。

关键判断依据是：数组里是否全是非负数（或者全为正数）。当所有元素非负时，右指针扩展窗口和只会变大，左指针收缩窗口和只会变小，窗口和具有单调性，于是可以用双指针滑动窗口做到 O(n) 时间和 O(1) 空间来求"和等于 k、和不超过 k"的问题。

一旦数组里出现负数，窗口和的单调性被打破，滑动窗口这套"小了往右扩、大了往左缩"的逻辑就会失效。这时就该切回前缀和加哈希表的方案。560 和 974 的题目里明明有负数，所以滑动窗口在这两题上站不住脚，只能靠前缀和。

用表格总结一下选型逻辑：

5.4 常见变形题的迁移清单

学会了这套框架后，可以主动做几类迁移训练，巩固理解。

• 连续子数组的和为 k，求最短或最长长度：前缀和加哈希表，键从次数升级为首次出现的索引。
• 数组中奇数和偶数个数相等的子数组：把奇数记为 1、偶数记为 -1，问题变成区间和为 0 的计数，直接套 560 的模板。
• 子数组的和能被 k 整除的最长子数组：和 974 类似，但哈希表存"某个余数第一次出现的位置"，贪心留最远的索引。
• 前缀异或和数组：异或运算满足"区间异或 = 前缀异或之差"，与加法前缀和的地位完全对称，原理可以类推。

这些变体看起来千差万别，考的还是同一件事：能否把连续段的特征消去中间过程，转化为两个"前缀状态"的关系。

6. 刷题实战中的坑与面试表达技巧

6.1 我踩过的三个坑，逐个复盘

第一，先查后更新的顺序问题。我在 560 题上翻过车，输入nums = [1], k = 0，答案是 0，但如果不小心先更新cnt再查询，当前前缀和cur = 1会被先加入表中，接着查cur - 0 = 1会命中自己，错误输出 1。如果以后遇到k=0的题，第一反应就要检查先查还是先更新。

第二，负数取模修正缺失。写 974 的 C++ 版时，我第一次用的代码是int mod = cur % k;，样例nums = [-1, 5], k = 5直接挂掉。原因在于cur=-1时 C++ 返回-1，数组访问越界。当时调试了好久才发现问题出在那个负号上。教训是看到"整除"两个字，先看语言对负数的取模行为。

第三，空间复杂度的过度设计。974 的k <= 10^4，用vector<int> cnt(k, 0)就够了，我却一上来就写unordered_map<int, int>，虽然功能对，但面试官问到"能不能优化空间"时反而显得没思考。余数范围已知的情况下，数组一定优先于哈希表；只有键值域稀疏或不确定时才考虑哈希表。这是工程思维在算法题里的体现。

6.2 边界条件与溢出问题

边界条件主要考虑三类。数组长度为 1 时，只有一个子数组nums[0]本身，判断它是否满足条件即可，代码逻辑天然覆盖；前缀和所有元素之和本身就是某个状态，要确保计数准确；cur - k可能超出 int 范围吗？根据题目限制，nums[i]最大10^4，长度最多2*10^4，前缀和绝对值的最大值是2*10^8，仍在 32 位 int 范围内（约 21 亿）。所以这里用 int 是安全的，但如果你自己写测试时放大了数据范围，建议果断换long long。这些边界思考在面试中提一句，会显得你很严谨。

6.3 面试时怎么把解法讲得清楚又加分

很多同学会写代码但讲不清楚思路，面试官最反感的就是"死记模板答案"。我的建议是按推理链条来表述。

第一步承认暴力：枚举所有左右端点 O(n²)，n 到两万时会超时，需要更低复杂度。第二步引入前缀和：区间和能用前缀和的差表示，把"区间"问题变成"两个数之差"问题。第三步用哈希表消去一维枚举：固定右端点后，只需查历史前缀和，于是 O(n²) 降到 O(n)。第四步补细节：说明初始化cnt[0]=1的含义，以及 974 题里负数取模为什么要修正，最好顺手写出修正公式。

这套讲法的好处是每一步都有明确理由，面试官能看出你是真的理解，而不是背题。如果遇到追问"为什么空间是 O(k)"，直接把余数范围讲出来即可。

最后再分享一个小技巧：学前缀和我建议在草稿纸上画两条线，一条是原始数组，一条是对应的前缀和数组。手动标出每个位置的前缀和值，再画出哪些下标对满足等式。画过一遍之后，cnt[0]=1就不会再像魔法一样神秘，它只是"空前缀状态"的占位记号。这两道题吃透了，后面再遇到二维前缀和、树上前缀和、以及各种"子数组满足某条件"的变体，都会回到同一个核心问题：区间状态能否改写成两个前缀状态之差。想通这一点，刷题效率会比盲目堆量高很多。