做了七年算法教学最常被问到的就是前缀和到底在解决什么问题。这个疑问一般来自 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个。第三组例子特意带了负数和k0因为后面你会发现k0的情况最容易把初学者坑进计数重复的陷阱里。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天的累计花费那么从第j1天到第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子数组才能是空区间以外的合法区间。如果把自己也算进去当k0时就会出现明显的虚增。2.2 用哈希表记录前缀和值出现次数既然题目只要求统计个数不需要回传具体区间那么哈希表的键可以设为前缀和的值值设为该前缀和已经出现的次数。扫描数组时维护一个计数器逻辑累加当前前缀和cur查询哈希表中cur - k的出现次数把结果加入答案把当前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(vectorint nums, int k) { unordered_mapint, 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 0ans 0处理x 1cur 1查cnt[-1] 0ans 0更新cnt[1] 1处理x 1cur 2查cnt[0] 1ans 1更新cnt[2] 1处理x 1cur 3查cnt[1] 1ans 2更新cnt[3] 1最后ans 2与预期完全一致。第一个满足条件的子数组来自j-1对应的空前缀第二个来自前缀和pre[1] 1和pre[3] 3的差值。当cur2时查cnt[0]命中的就是cnt[0]1这个初始化值这正说明了cnt[0]1的重要性。再试一个带负数的例子nums [-1, -1, 1], k 0。初始cnt {0: 1}处理-1cur -1查cnt[-1] 0更新cnt[-1] 1ans 0处理-1cur -2查cnt[-2] 0更新cnt[-2] 1ans 0处理1cur -1查cnt[-1] 1ans 1更新cnt[-1] 2最终ans 1也就是[-1, 1]这段正确。注意哈希表的键值完全可以是负数C 的unordered_mapint, int和 Python 的 dict 都支持负整数键。2.5 复杂度与空间取舍分析单次遍历数组哈希表查询和更新都是平均O(1)整体时间O(n)。空间上最坏情况下前缀和的值可能每个都不同哈希表最多存n1个键所以空间O(n)。这里还有一个值得说的点在这个问题里哈希表只存出现次数就够用了不需要存索引列表。因为题目要的是数量不是要你输出具体是哪些区间。如果题目改成找出和为 k 的最短子数组长度或者输出所有合法区间哈希表才需要升级成值 - 索引列表的映射。这也是为什么我一再强调审题重要同样是子数组和问题题目诉求不同数据结构的设计就不同。3. 和可被k整除的子数组同余定理上场负数取模才是真正的坑3.1 题目描述第二题比第一题多了什么第 974 题的描述是给定一个整数数组nums和一个整数k返回其中和可被k整除的连续、非空子数组的数目。nums的长度同样是1 n 2 * 10^4但k的范围是1 k 10^4注意这里的k为正整数不存在k0的情况。nums[i]的范围是-10^4 nums[i] 10^4负数是一定会出现的。相比 560 题这里的条件从区间和恰好等于一个数变成了区间和是一个数的整数倍。如果你上来就用暴力枚举复杂度依然爆炸。而用前缀和的思路区间和是pre[i] - pre[j]目标条件变成(pre[i] - pre[j]) % k 03.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(vectorint nums, int k) { vectorint 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] 1cur 0处理4cur 4mod 4cnt[4]0随后cnt[4]1处理5cur 9mod 4cnt[4]1ans1cnt[4]2子数组[4,5]模5为4前缀和4和9同余处理0cur 9mod 4cn t[4]2ans3cnt[4]3这里[0]、[4,5]、[4,5,0]都计入了处理-2cur 7mod 2cnt[2]0随后cnt[2]1处理-3cur 4mod 4cnt[4]3ans6cnt[4]4处理1cur 5mod 0cnt[0]1ans7cnt[0]2最终 7与题目输出一致。注意最后cur5mod0时命中的是cnt[0]1这意味着整个数组[4,5,0,-2,-3,1]的和 5 能被 5 整除是一个从下标 0 开始的合法子数组再次印证了cnt[0] 1的初始化价值。4. 把两道题放在一起看抽象出一个两数之差哈希计数的通法4.1 两题对比表相似写法与致命差异560 和 974 刷完之后最好做一次横向对比不然下次换一道变形题还是容易懵。对比维度560 和为 k 的子数组974 和可被 k 整除的子数组目标等式pre[i] - pre[j] k(pre[i] - pre[j]) % k 0哈希表/数组的键前缀和的值前缀和对 k 取模的余数查询逻辑ans cnt[cur - k]mod (cur % k k) % k; ans cnt[mod]负数处理不需要特别修正C 必须修正负数取模空间开销O(n)用哈希表O(k)用定长数组更优典型隐藏坑k0时先查后更新的顺序负数取模导致键不匹配两张表看下来会发现 974 几乎就是 560 的镜像把值换成余数把差等于 k换成差被 k 整除剩下的循环结构、更新顺序、初始化方法一字不改。这就是为什么说前缀和专题是一通百通的题型——你掌握了其中一题的骨架另一题只是换了件马甲。4.2 为什么第二题在实际刷题中更常卡壳从我在群里看到的提问频率来说974 的平均卡壳概率明显高于 560。原因不外乎三点。第一取模符号问题。C 和 Java 的%对负数不友好这属于语言层面的坑很多人第一次见根本意识不到-2和3竟然要归入同一个桶。第二cnt[0] 1在两题中的含义被误读。560 里它代表空前缀和的值为 0974 里它代表空前缀和的余数为 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 的题目里明明有负数所以滑动窗口在这两题上站不住脚只能靠前缀和。用表格总结一下选型逻辑条件推荐方案理由数组全为非负数求满足和的窗口滑动窗口单调性保证 O(n)空间 O(1)数组含负数连续子数组计数前缀和 哈希表突破单调性限制O(n) 时间需要求具体区间位置前缀和 哈希表存索引同时记录首次出现位置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。如果以后遇到k0的题第一反应就要检查先查还是先更新。第二负数取模修正缺失。写 974 的 C 版时我第一次用的代码是int mod cur % k;样例nums [-1, 5], k 5直接挂掉。原因在于cur-1时 C 返回-1数组访问越界。当时调试了好久才发现问题出在那个负号上。教训是看到整除两个字先看语言对负数的取模行为。第三空间复杂度的过度设计。974 的k 10^4用vectorint cnt(k, 0)就够了我却一上来就写unordered_mapint, 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就不会再像魔法一样神秘它只是空前缀状态的占位记号。这两道题吃透了后面再遇到二维前缀和、树上前缀和、以及各种子数组满足某条件的变体都会回到同一个核心问题区间状态能否改写成两个前缀状态之差。想通这一点刷题效率会比盲目堆量高很多。