1. 从“区间求和”说起——为什么我坚持把前缀和放进集训第14天很多算法初学者第一次接触前缀和是在 LeetCode 的“区域和检索”这类题上。题目很直白给你一个数组反复求某个区间[l, r]的和调用很多次怎么做到每次都很快。暴力解法谁都会一个循环累加就完了但问题是数据量上来之后一次 O(n) 的查询在成百上千次调用面前很快就撑不住了。前缀和就是为这种“频繁区间查询”量身定做的解法它把每次查询的复杂度从 O(n) 压到 O(1)代价是提前花 O(n) 的时间和空间做一次预处理。我把前缀和放在集训第 14 天不是因为它难恰恰是因为它简单、基础却又极其常用。它是算法竞赛和面试题里“高频词”也是很多进阶题型的地基比如二维前缀和、带权前缀和、前缀和配哈希表、差分与前缀和的配合。你把这一个点吃透等于一次拿下了一整类题。这篇文章我就按自己带集训的做法把前缀和从模板到变形、从原理到实战、从坑点到技巧完整梳理一遍希望能帮你一次性把它打穿。2. 前缀和到底解决什么问题——先弄清楚它为什么值得学2.1 一个高频场景反复求区间和先说最朴素的需求。假设你维护了一个数组比如每个元素是某个班级学生一周内每天的作业提交数老师想反复统计第 2 天到第 5 天一共交了多少份作业。单次统计很简单把第 2 到第 5 天的数字加起来就行。但如果老师用这套接口去统计所有 30 天的所有区间而且每天要统计几百次呢每次循环累加的时间成本就会变成一个很扎眼的 O(n) 复杂度总成本直接变成 O(n×m)n 是数组长度m 是查询次数。暴力解法的问题不是“算不对”而是“算得太慢”。这时候你注意到一件事如果我事先把“从第 1 天到第 i 天的累计提交数”全部算好那第 2 天到第 5 天的和就等于“第 1 到第 5 天的累计数”减去“第 1 到第 1 天的累计数”。这个减法的结果是 O(1) 的。这就是前缀和的全部秘密。它把“区间求和”问题转换成了“两个前缀和相减”问题相当于把查询阶段的工作量全部转移到了预处理阶段。预处理只做一次查询却可能有很多次这笔账怎么算都划算。2.2 前缀和的核心思想与数学定义前缀和的定义写出来很简单给定数组nums其长度为 n前缀和数组prefix满足prefix[i] nums[0] nums[1] ... nums[i]也就是prefix[i]表示数组中下标从 0 到 i 的所有元素之和。那么要计算原数组区间[l, r]的和直接用sum(l, r) prefix[r] - prefix[l - 1]当l 0时prefix[l - 1]不存在所以习惯上我们把前缀和数组前移一位让prefix[k]表示前 k 个元素的和。这样prefix[0] 0 prefix[k] prefix[k - 1] nums[k - 1] // k 从 1 到 n sum(l, r) prefix[r 1] - prefix[l]这里用的是“前 k 个元素和”的版本代码里非常常见因为它天然规避了l 0的边界问题。两种表示本质上是等价的但后者写起来更顺、更好维护。2.3 为什么前缀和不只是“累加一遍”有人会问前缀和不就是for循环累加吗有什么值得学的。我一般这么回答从代码写法上看确实简单但它背后是一种“空间换时间”的预处理思想。你需要建立这种意识——当一类查询会反复执行时先把可以预先计算的东西都算好之后每次查询直接查表。这个思维模式在前缀和、后缀和、哈希表、稀疏表、树状数组里一脉相承。学会了前缀和你再去碰其他更复杂的结构会明显感觉思路顺很多。这也是我坚持在基础阶段就反复训练这种“预处理思维”的原因。3. 一维前缀和的完整实现——模板、边界与代码细节3.1 最基础的一维前缀和模板我用 Python 写一个最标准的版本def build_prefix(nums): n len(nums) prefix [0] * (n 1) # prefix[i] 表示 nums 前 i 个元素的和 for i in range(1, n 1): prefix[i] prefix[i - 1] nums[i - 1] return prefix def range_sum(prefix, l, r): # 求 nums[l..r] 的和闭区间 return prefix[r 1] - prefix[l]在这个模板里prefix的长度是n 1多出的prefix[0]作为哨兵值。求下标从l到r的闭区间和直接prefix[r 1] - prefix[l]就结束了。我故意让写法固定下来因为固定可以让你的大脑形成肌肉记忆比赛或面试时少想一层。C 版本也是同样套路vectorint buildPrefix(vectorint nums) { int n nums.size(); vectorint prefix(n 1, 0); for (int i 1; i n; i) { prefix[i] prefix[i - 1] nums[i - 1]; } return prefix; } int rangeSum(vectorint prefix, int l, int r) { return prefix[r 1] - prefix[l]; }3.2 下标到底怎么设——这是我见过最多的翻车点很多初学者写前缀和最容易错的地方不是逻辑而是下标。我自己集训的时候见过不下于十次这种错误prefix[i] prefix[i - 1] nums[i]然后访问prefix[i]越界。原因就是把“前 i 个元素之和”和“下标 i 对应元素”混在一块了。我建议你从一开始就给自己定一条铁律prefix[i]永远表示“前 i 个元素的和”而不是“下标 0 到 i 的和”。一旦确定这个约定nums和prefix之间就错开了 1 位初始化、循环、区间求和全部按这个约定来。这个固定的错位关系看着有点绕但正因为绕所以值得你多花几分钟在纸上画一遍画通了后面所有题都不怕。3.3 边界情况的处理边界情况主要分三种。第一种是空数组n 0时prefix只有[0]不会报错。第二种是查询l r也就是单点查询直接用prefix[r 1] - prefix[r]得到的就是nums[r]这个结果天然正确。第三种是查询l 0此时prefix[0] 0也天然处理好了。只要模板写得统一这些边界情况基本不用单独处理这也是“前 k 个元素”版本的优势所在。4. 二维前缀和——子矩阵求和的利器4.1 从一维到二维思路的延伸一维前缀和在数组上用二维前缀和就在矩阵上用。解决的问题也从“区间和”升级成了“子矩阵和”。比如给出一个 m×n 的矩阵反复查询某个子矩形区域内所有元素之和。最暴力的做法是四重循环查询一次 O(m×n)。二维前缀和可以把每次查询优化到 O(1)。思路完全延续一维的套路但需要多考虑一个维度上的叠加。定义pre[i][j]表示以(0,0)为左上角、(i-1,j-1)为右下角的子矩阵所有元素之和。这里延续“前 k 个”的约定让pre的大小为(m1)×(n1)方便处理边界。递推公式是pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] matrix[i-1][j-1]这个公式看起来有点奇怪但原理很好懂要算(0,0) 到 (i-1,j-1)的矩形和可以先加上“少了最上面一行”的部分再加上“少了最左边一列”的部分但这样一来左上角那一块被加了两次所以要减掉一次最后再把当前元素matrix[i-1][j-1]加上去。你可以想象成拼拼图或者用韦恩图来理解“加多减回”的过程。查询子矩阵(r1,c1)到(r2,c2)的和时同样用容斥sum pre[r21][c21] - pre[r1][c21] - pre[r21][c1] pre[r1][c1]这个公式对应的就是把大的矩形拆成三块剪掉、再加回被重复剪掉的那一块。4.2 一个经典题目最大子矩阵和力扣第 304 题“二维区域和检索”就是二维前缀和的直接应用。题目给定一个矩阵和一系列查询每次查询给一个子矩形的左上角和右下角返回子矩形元素之和。如果矩阵是固定的查询却很多次前缀和方案可以说是标准答案。实现时我先写一个初始化函数class NumMatrix: def __init__(self, matrix): m, n len(matrix), len(matrix[0]) self.pre [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): self.pre[i][j] ( self.pre[i-1][j] self.pre[i][j-1] - self.pre[i-1][j-1] matrix[i-1][j-1] ) def sumRegion(self, r1, c1, r2, c2): return ( self.pre[r21][c21] - self.pre[r1][c21] - self.pre[r21][c1] self.pre[r1][c1] )代码本身就这么点。真正容易踩坑的是初始化时m和n的取值以及for循环里matrix的下标要减 1。我见过太多人写matrix[i][j]而不是matrix[i-1][j-1]导致初始化直接下标越界。4.3 二维前缀和的细节坑二维比一维多出来的三个坑我逐个说。第一个坑是空间复杂度。pre数组的大小是(m1)×(n1)在 m、n 都很大时内存要多出来一整行和整列虽然影响不大但你要有这个认知尤其是做竞赛题时题目给的内存限制可能很抠。第二个坑是pre的类型。矩阵元素之和可能很大C 里建议直接用long long避免中间运算溢出。Python 没这个问题但面试时用其他语言就要留意。第三个坑是递推顺序。二维前缀和必须按行从上到下、每行从左到右递推因为pre[i][j]依赖pre[i-1][j]、pre[i][j-1]和pre[i-1][j-1]如果循环顺序乱了算出来的值全是错的。这个错误不太会报异常只会默默给出错误答案属于“隐蔽性很强”的 bug。5. 前缀和配哈希表——解决“子数组和为 K”这一类题5.1 核心思路如果说纯前缀和只是基础那“前缀和哈希表”就是面试里真正的高频考点了。最典型的题是 LeetCode 560“和为 K 的子数组”。题目要求统计数组中有多少个子数组的和等于K。直接用前缀和数组可以做枚举每个子数组的左右端点然后求和判断复杂度 O(n²)。但如果配合哈希表可以优化到 O(n)。具体思路是遍历数组时我们维护当前前缀和cur。如果存在某个历史前缀和prev满足cur - prev K那么这个区间对应的子数组和为 K。也就是说我们要在“已经出现过的前缀和”里查找有多少个cur - K。哈希表正好保存了每个前缀和出现的次数这样每次查找都是 O(1)。5.2 哈希表细节为什么初始化要把 {0: 1} 放进去这道题有一个新手特别容易忽略的细节初始化哈希表时要放进{0: 1}代表“前缀和为 0 出现过一次”。为什么因为如果这个子数组恰好是从下标 0 开始的那么对应的prev就是 0。比如数组是[1, 2, 3]K 3在遍历到下标 1 时cur 3此时需要找cur - K 0如果哈希表里没有 0就会漏掉[0, 1]这个子数组答案就错了。这个细节我每次讲题都会强调一遍因为它太隐蔽了尤其在没有样例覆盖这类情况时非常容易写出看似正确但结果差 1 的代码。5.3 模板与代码def subarraySum(nums, k): prefix_count {0: 1} cur 0 ans 0 for num in nums: cur num # 当前前缀和减去 K如果之前出现过说明存在和为 K 的子数组 ans prefix_count.get(cur - k, 0) prefix_count[cur] prefix_count.get(cur, 0) 1 return ans要注意的是更新哈希表的顺序必须放在查询之后。如果先更新再查询会出现同一个位置被重复统计的情况比如cur K时会误把当前整个前缀当作子数组再额外加一次答案就会偏大。我第一次给集训学员讲这道题的时候至少有两个人踩了这个顺序的坑所以我把它专门拎出来说。5.4 这类题的变体“前缀和哈希表”不只是“和为 K”一种考法。把条件换成“和能被 K 整除的子数组”就是 LeetCode 974换成“和为 K 的最长子数组”就是返回长度而不是数量如果数组里只有 0 和 1把 0 看成 -1那么“和为 0 的子数组”就等价于“0 和 1 数量相等的子数组”这就和 LeetCode 525 连上了。思路永远是同一个把前缀和之间的关系用哈希表快速查找而不是枚举所有端点。6. 前缀和与差分——一对互补的思路6.1 差分是什么和前缀和有什么关系差分可以看成前缀和的逆运算。前缀和是把一个数组的累计信息算出来而差分则是把原数组“还原成变化量”。给定数组nums它的差分数组diff[i] nums[i] - nums[i-1]。有意思的是如果对差分数组做一次前缀和你会得到原数组。反过来对原数组做前缀和你会得到累计数组。这两个操作是一对互逆的变换。这个性质在算法里特别有用。比如要对数组的某个区间[l, r]统一加上一个值x如果直接循环改复杂度 O(n)。但如果用差分数组只需要diff[l] x、diff[r1] - x最后再做一次前缀和还原就能把所有区间更新批量完成总复杂度 O(n 更新次数)。这在处理“多次区间更新、最后统一查询”的场景里非常高效。6.2 什么时候用前缀和什么时候用差分我做题时习惯这么判断题目要你“多次查询区间和”就用前缀和题目要你“多次更新区间值最后批量查询”就用差分。一个负责快速的查询一个负责快速的区间更新。两者还经常出现在同一道题里。比如 LeetCode 1109“航班预订统计”就是典型的差分题。你先把每条预订记录对应到差分数组上做几次 O(1) 的修改最后再扫一遍前缀和生成结果。这类题在整个基础集训阶段我一般会跟前缀和放在相邻的几天讲让学员能自然地把两个概念联系起来。6.3 一个小的综合示例我举个例子来说明配合过程。假设一个长度为 5 的全 0 数组要执行两次操作第一次在区间 [1, 3] 加 2第二次在区间 [2, 4] 加 3。如果用差分先建全 0 的差分数组第一次操作令diff[1] 2、diff[4] - 2第二次令diff[2] 3、diff[5] - 3。然后从前往后做一遍前缀和下标diff前缀和还原结果0001222353054-235-30你看中间两个区间同时累加了两次操作的效果而两边没有受影响。这个思路在“区间更新、区间查询”类问题里是一把钥匙。7. 实战复盘——LeetCode 经典前缀和题型的手写过程7.1 第 303 题区域和检索-数组不可变这道题是前缀和最直接的模板题非常适合用来检验自己有没有把模板写熟。题目给定一个整数数组nums让你实现一个类支持多次调用sumRange(l, r)求闭区间[l, r]的和。我的做法就是标准的“前 k 个元素之和”版本class NumArray: def __init__(self, nums): self.prefix [0] for x in nums: self.prefix.append(self.prefix[-1] x) def sumRange(self, l, r): return self.prefix[r 1] - self.prefix[l]这段代码非常短但信息密度很高。self.prefix初始化为一个包含 0 的列表然后逐个追加前缀和sumRange里直接用下标相减。我让集训学员在纸上把这个类的构造过程画一遍尤其是prefix长度和nums长度的关系以及sumRange里下标r 1和l的由来。把这些彻底想明白了一维前缀和就不会再有问题。7.2 第 724 题寻找数组的中心下标这道题表面上是“找中间位置”但本质还是前缀和的应用。题目要求找到一个下标i使得左边所有元素之和等于右边所有元素之和。常规做法是总数减去当前元素再减去左边和得到右边和然后比较。我先算出总和total再从左到右维护左边和left_sum右边和就等于total - left_sum - nums[i]。判断二者相等即可。def pivotIndex(nums): total sum(nums) left_sum 0 for i, x in enumerate(nums): if left_sum total - left_sum - x: return i left_sum x return -1这里虽然没有显式构造前缀和数组但思路完全建立在“两侧和的对比”上属于前缀和思想的灵活应用。很多学员觉得“只有建了数组才叫前缀和”其实不是前缀和更多的是一种累计思考方式。7.3 第 974 题和可被 K 整除的子数组这道题也算“前缀和哈希表”的经典变体。因为同余性质如果两个前缀和对 K 的余数相同那么它们之间的区间和就能被 K 整除。所以在遍历时维护当前cur计算mod cur % K然后在哈希表里查找相同余数出现过的次数。被 5.3 的模板直接扩展一下就行核心代码几乎不变。8. 我在集训中反复踩过的坑——前缀和的 4 个高频错误8.1 下标越界与差一错误前缀和数组比原数组多了一位prefix的最后一格对应的是所有元素之和访问prefix[n]是合法的但如果你把下标搞混很容易访问prefix[n1]或prefix[-1]。这类问题我在给学员改代码时看到最多解决办法就是严格按照“前 k 个元素”的约定写并在测试用例里故意算一个l0、rn-1的全区间和。8.2 循环里更新哈希表的顺序错了如第 5.3 节所说“先查询后更新”是铁律。这个顺序一旦反过来重复统计的问题就会立刻出现而且答案往往差得不多特别难排查。我建议在代码里加个注释把这个顺序写明白防止面试时一紧张就写反。8.3 二维前缀和忘了减 1二维前缀和里matrix[i-1][j-1]的下标问题太容易错了。很多人初学时会写成matrix[i][j]然后发现越界。我自己的习惯是先把pre的大小定为(m1)×(n1)然后在双重循环的第一行写清楚注释“matrix 下标要减 1”每次写代码之前默念一遍。8.4 忘了开 long long 或处理负数取模C 做题时如果题目数据范围大前缀和相加可能溢出int。我通常会直接开vectorlong long省得事后 debug。另外像 LeetCode 974 这种“被 K 整除”的题负数的取模跟 C 的%行为可能和你预期不一致建议用((cur % K) K) % K来规范到非负余数这也是一个常见的隐藏雷点。9. 给不同阶段读者的建议——前缀和怎么练才有效如果是完全没接触过前缀和的新手我建议先不要碰难题老老实实做三件事。第一把一维模板背熟然后在纸上手算一个小数组的前缀和和区间查询验证结果。第二把 LeetCode 303 和 724 独立写出来不要看题解。第三再做几道纯模板题比如 LeetCode 1480“一维数组的动态和”感受一下“累加”到“前缀和”的无缝衔接。如果已经能写模板了就进入第二阶段掌握“前缀和哈希表”的题型。重点做 LeetCode 560、974、525把思路提炼成统一的模式。我个人建议每道题在 AC 之后再想一想如果题目改成“子数组长度至少为 2”“不能包含某个值”等条件代码要怎么改。这个扩展思考能帮你在面试官出变体时不至于当场卡壳。第三阶段就是把前缀和扩展到二维配合矩阵类题目做练习。做了 LeetCode 304 之后可以顺手看看 1074“元素和为目标值的子矩阵数量”那道题需要把二维问题按行压缩成一维再用哈希表优化是二维前缀和和“前缀和哈希表”的结合题型。建议在你把前两个阶段都夯实了之后再去碰。10. 关于前缀和我最后想说的几句话我做了这么多年算法相关的学习和带新人越来越觉得前缀和这种基础算法被严重低估了。你说它难吗模板背下来一段代码就能写。但它背后的“预处理空间换时间”的思想是很多高效算法的共同根基。面试官爱考它不是因为题本身有多难而是因为它能快速检验一个人有没有建立“高频查询之前先做预处理”的思维习惯。我个人在实际集训中还有一个体会前缀和这类基础算法最忌讳的是“看懂了、没写熟”。很多学员看一遍题解觉得会了结果两天后连模板都敲不利索。所以我会建议他们把它当成键盘肌肉记忆的一部分写到不用过脑子就能输出正确模板的程度。等到后面学差分、树状数组、线段树时你会发现前期这个熟练度带来的收益非常明显。最后分享一个我自己实践过的小技巧每学一个新算法就把它和已经学过的算法对比一下找出联系和区别。前缀和、差分、滑动窗口三兄弟经常出现在同一套题里你如果能在做题时主动判断“这题该用哪个”进步会快很多。希望这篇总结对你有帮助也欢迎你带着自己的实战问题来找我聊。
前缀和算法详解：从一维到二维，再到哈希表与差分的进阶应用
1. 从“区间求和”说起——为什么我坚持把前缀和放进集训第14天很多算法初学者第一次接触前缀和是在 LeetCode 的“区域和检索”这类题上。题目很直白给你一个数组反复求某个区间[l, r]的和调用很多次怎么做到每次都很快。暴力解法谁都会一个循环累加就完了但问题是数据量上来之后一次 O(n) 的查询在成百上千次调用面前很快就撑不住了。前缀和就是为这种“频繁区间查询”量身定做的解法它把每次查询的复杂度从 O(n) 压到 O(1)代价是提前花 O(n) 的时间和空间做一次预处理。我把前缀和放在集训第 14 天不是因为它难恰恰是因为它简单、基础却又极其常用。它是算法竞赛和面试题里“高频词”也是很多进阶题型的地基比如二维前缀和、带权前缀和、前缀和配哈希表、差分与前缀和的配合。你把这一个点吃透等于一次拿下了一整类题。这篇文章我就按自己带集训的做法把前缀和从模板到变形、从原理到实战、从坑点到技巧完整梳理一遍希望能帮你一次性把它打穿。2. 前缀和到底解决什么问题——先弄清楚它为什么值得学2.1 一个高频场景反复求区间和先说最朴素的需求。假设你维护了一个数组比如每个元素是某个班级学生一周内每天的作业提交数老师想反复统计第 2 天到第 5 天一共交了多少份作业。单次统计很简单把第 2 到第 5 天的数字加起来就行。但如果老师用这套接口去统计所有 30 天的所有区间而且每天要统计几百次呢每次循环累加的时间成本就会变成一个很扎眼的 O(n) 复杂度总成本直接变成 O(n×m)n 是数组长度m 是查询次数。暴力解法的问题不是“算不对”而是“算得太慢”。这时候你注意到一件事如果我事先把“从第 1 天到第 i 天的累计提交数”全部算好那第 2 天到第 5 天的和就等于“第 1 到第 5 天的累计数”减去“第 1 到第 1 天的累计数”。这个减法的结果是 O(1) 的。这就是前缀和的全部秘密。它把“区间求和”问题转换成了“两个前缀和相减”问题相当于把查询阶段的工作量全部转移到了预处理阶段。预处理只做一次查询却可能有很多次这笔账怎么算都划算。2.2 前缀和的核心思想与数学定义前缀和的定义写出来很简单给定数组nums其长度为 n前缀和数组prefix满足prefix[i] nums[0] nums[1] ... nums[i]也就是prefix[i]表示数组中下标从 0 到 i 的所有元素之和。那么要计算原数组区间[l, r]的和直接用sum(l, r) prefix[r] - prefix[l - 1]当l 0时prefix[l - 1]不存在所以习惯上我们把前缀和数组前移一位让prefix[k]表示前 k 个元素的和。这样prefix[0] 0 prefix[k] prefix[k - 1] nums[k - 1] // k 从 1 到 n sum(l, r) prefix[r 1] - prefix[l]这里用的是“前 k 个元素和”的版本代码里非常常见因为它天然规避了l 0的边界问题。两种表示本质上是等价的但后者写起来更顺、更好维护。2.3 为什么前缀和不只是“累加一遍”有人会问前缀和不就是for循环累加吗有什么值得学的。我一般这么回答从代码写法上看确实简单但它背后是一种“空间换时间”的预处理思想。你需要建立这种意识——当一类查询会反复执行时先把可以预先计算的东西都算好之后每次查询直接查表。这个思维模式在前缀和、后缀和、哈希表、稀疏表、树状数组里一脉相承。学会了前缀和你再去碰其他更复杂的结构会明显感觉思路顺很多。这也是我坚持在基础阶段就反复训练这种“预处理思维”的原因。3. 一维前缀和的完整实现——模板、边界与代码细节3.1 最基础的一维前缀和模板我用 Python 写一个最标准的版本def build_prefix(nums): n len(nums) prefix [0] * (n 1) # prefix[i] 表示 nums 前 i 个元素的和 for i in range(1, n 1): prefix[i] prefix[i - 1] nums[i - 1] return prefix def range_sum(prefix, l, r): # 求 nums[l..r] 的和闭区间 return prefix[r 1] - prefix[l]在这个模板里prefix的长度是n 1多出的prefix[0]作为哨兵值。求下标从l到r的闭区间和直接prefix[r 1] - prefix[l]就结束了。我故意让写法固定下来因为固定可以让你的大脑形成肌肉记忆比赛或面试时少想一层。C 版本也是同样套路vectorint buildPrefix(vectorint nums) { int n nums.size(); vectorint prefix(n 1, 0); for (int i 1; i n; i) { prefix[i] prefix[i - 1] nums[i - 1]; } return prefix; } int rangeSum(vectorint prefix, int l, int r) { return prefix[r 1] - prefix[l]; }3.2 下标到底怎么设——这是我见过最多的翻车点很多初学者写前缀和最容易错的地方不是逻辑而是下标。我自己集训的时候见过不下于十次这种错误prefix[i] prefix[i - 1] nums[i]然后访问prefix[i]越界。原因就是把“前 i 个元素之和”和“下标 i 对应元素”混在一块了。我建议你从一开始就给自己定一条铁律prefix[i]永远表示“前 i 个元素的和”而不是“下标 0 到 i 的和”。一旦确定这个约定nums和prefix之间就错开了 1 位初始化、循环、区间求和全部按这个约定来。这个固定的错位关系看着有点绕但正因为绕所以值得你多花几分钟在纸上画一遍画通了后面所有题都不怕。3.3 边界情况的处理边界情况主要分三种。第一种是空数组n 0时prefix只有[0]不会报错。第二种是查询l r也就是单点查询直接用prefix[r 1] - prefix[r]得到的就是nums[r]这个结果天然正确。第三种是查询l 0此时prefix[0] 0也天然处理好了。只要模板写得统一这些边界情况基本不用单独处理这也是“前 k 个元素”版本的优势所在。4. 二维前缀和——子矩阵求和的利器4.1 从一维到二维思路的延伸一维前缀和在数组上用二维前缀和就在矩阵上用。解决的问题也从“区间和”升级成了“子矩阵和”。比如给出一个 m×n 的矩阵反复查询某个子矩形区域内所有元素之和。最暴力的做法是四重循环查询一次 O(m×n)。二维前缀和可以把每次查询优化到 O(1)。思路完全延续一维的套路但需要多考虑一个维度上的叠加。定义pre[i][j]表示以(0,0)为左上角、(i-1,j-1)为右下角的子矩阵所有元素之和。这里延续“前 k 个”的约定让pre的大小为(m1)×(n1)方便处理边界。递推公式是pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] matrix[i-1][j-1]这个公式看起来有点奇怪但原理很好懂要算(0,0) 到 (i-1,j-1)的矩形和可以先加上“少了最上面一行”的部分再加上“少了最左边一列”的部分但这样一来左上角那一块被加了两次所以要减掉一次最后再把当前元素matrix[i-1][j-1]加上去。你可以想象成拼拼图或者用韦恩图来理解“加多减回”的过程。查询子矩阵(r1,c1)到(r2,c2)的和时同样用容斥sum pre[r21][c21] - pre[r1][c21] - pre[r21][c1] pre[r1][c1]这个公式对应的就是把大的矩形拆成三块剪掉、再加回被重复剪掉的那一块。4.2 一个经典题目最大子矩阵和力扣第 304 题“二维区域和检索”就是二维前缀和的直接应用。题目给定一个矩阵和一系列查询每次查询给一个子矩形的左上角和右下角返回子矩形元素之和。如果矩阵是固定的查询却很多次前缀和方案可以说是标准答案。实现时我先写一个初始化函数class NumMatrix: def __init__(self, matrix): m, n len(matrix), len(matrix[0]) self.pre [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): self.pre[i][j] ( self.pre[i-1][j] self.pre[i][j-1] - self.pre[i-1][j-1] matrix[i-1][j-1] ) def sumRegion(self, r1, c1, r2, c2): return ( self.pre[r21][c21] - self.pre[r1][c21] - self.pre[r21][c1] self.pre[r1][c1] )代码本身就这么点。真正容易踩坑的是初始化时m和n的取值以及for循环里matrix的下标要减 1。我见过太多人写matrix[i][j]而不是matrix[i-1][j-1]导致初始化直接下标越界。4.3 二维前缀和的细节坑二维比一维多出来的三个坑我逐个说。第一个坑是空间复杂度。pre数组的大小是(m1)×(n1)在 m、n 都很大时内存要多出来一整行和整列虽然影响不大但你要有这个认知尤其是做竞赛题时题目给的内存限制可能很抠。第二个坑是pre的类型。矩阵元素之和可能很大C 里建议直接用long long避免中间运算溢出。Python 没这个问题但面试时用其他语言就要留意。第三个坑是递推顺序。二维前缀和必须按行从上到下、每行从左到右递推因为pre[i][j]依赖pre[i-1][j]、pre[i][j-1]和pre[i-1][j-1]如果循环顺序乱了算出来的值全是错的。这个错误不太会报异常只会默默给出错误答案属于“隐蔽性很强”的 bug。5. 前缀和配哈希表——解决“子数组和为 K”这一类题5.1 核心思路如果说纯前缀和只是基础那“前缀和哈希表”就是面试里真正的高频考点了。最典型的题是 LeetCode 560“和为 K 的子数组”。题目要求统计数组中有多少个子数组的和等于K。直接用前缀和数组可以做枚举每个子数组的左右端点然后求和判断复杂度 O(n²)。但如果配合哈希表可以优化到 O(n)。具体思路是遍历数组时我们维护当前前缀和cur。如果存在某个历史前缀和prev满足cur - prev K那么这个区间对应的子数组和为 K。也就是说我们要在“已经出现过的前缀和”里查找有多少个cur - K。哈希表正好保存了每个前缀和出现的次数这样每次查找都是 O(1)。5.2 哈希表细节为什么初始化要把 {0: 1} 放进去这道题有一个新手特别容易忽略的细节初始化哈希表时要放进{0: 1}代表“前缀和为 0 出现过一次”。为什么因为如果这个子数组恰好是从下标 0 开始的那么对应的prev就是 0。比如数组是[1, 2, 3]K 3在遍历到下标 1 时cur 3此时需要找cur - K 0如果哈希表里没有 0就会漏掉[0, 1]这个子数组答案就错了。这个细节我每次讲题都会强调一遍因为它太隐蔽了尤其在没有样例覆盖这类情况时非常容易写出看似正确但结果差 1 的代码。5.3 模板与代码def subarraySum(nums, k): prefix_count {0: 1} cur 0 ans 0 for num in nums: cur num # 当前前缀和减去 K如果之前出现过说明存在和为 K 的子数组 ans prefix_count.get(cur - k, 0) prefix_count[cur] prefix_count.get(cur, 0) 1 return ans要注意的是更新哈希表的顺序必须放在查询之后。如果先更新再查询会出现同一个位置被重复统计的情况比如cur K时会误把当前整个前缀当作子数组再额外加一次答案就会偏大。我第一次给集训学员讲这道题的时候至少有两个人踩了这个顺序的坑所以我把它专门拎出来说。5.4 这类题的变体“前缀和哈希表”不只是“和为 K”一种考法。把条件换成“和能被 K 整除的子数组”就是 LeetCode 974换成“和为 K 的最长子数组”就是返回长度而不是数量如果数组里只有 0 和 1把 0 看成 -1那么“和为 0 的子数组”就等价于“0 和 1 数量相等的子数组”这就和 LeetCode 525 连上了。思路永远是同一个把前缀和之间的关系用哈希表快速查找而不是枚举所有端点。6. 前缀和与差分——一对互补的思路6.1 差分是什么和前缀和有什么关系差分可以看成前缀和的逆运算。前缀和是把一个数组的累计信息算出来而差分则是把原数组“还原成变化量”。给定数组nums它的差分数组diff[i] nums[i] - nums[i-1]。有意思的是如果对差分数组做一次前缀和你会得到原数组。反过来对原数组做前缀和你会得到累计数组。这两个操作是一对互逆的变换。这个性质在算法里特别有用。比如要对数组的某个区间[l, r]统一加上一个值x如果直接循环改复杂度 O(n)。但如果用差分数组只需要diff[l] x、diff[r1] - x最后再做一次前缀和还原就能把所有区间更新批量完成总复杂度 O(n 更新次数)。这在处理“多次区间更新、最后统一查询”的场景里非常高效。6.2 什么时候用前缀和什么时候用差分我做题时习惯这么判断题目要你“多次查询区间和”就用前缀和题目要你“多次更新区间值最后批量查询”就用差分。一个负责快速的查询一个负责快速的区间更新。两者还经常出现在同一道题里。比如 LeetCode 1109“航班预订统计”就是典型的差分题。你先把每条预订记录对应到差分数组上做几次 O(1) 的修改最后再扫一遍前缀和生成结果。这类题在整个基础集训阶段我一般会跟前缀和放在相邻的几天讲让学员能自然地把两个概念联系起来。6.3 一个小的综合示例我举个例子来说明配合过程。假设一个长度为 5 的全 0 数组要执行两次操作第一次在区间 [1, 3] 加 2第二次在区间 [2, 4] 加 3。如果用差分先建全 0 的差分数组第一次操作令diff[1] 2、diff[4] - 2第二次令diff[2] 3、diff[5] - 3。然后从前往后做一遍前缀和下标diff前缀和还原结果0001222353054-235-30你看中间两个区间同时累加了两次操作的效果而两边没有受影响。这个思路在“区间更新、区间查询”类问题里是一把钥匙。7. 实战复盘——LeetCode 经典前缀和题型的手写过程7.1 第 303 题区域和检索-数组不可变这道题是前缀和最直接的模板题非常适合用来检验自己有没有把模板写熟。题目给定一个整数数组nums让你实现一个类支持多次调用sumRange(l, r)求闭区间[l, r]的和。我的做法就是标准的“前 k 个元素之和”版本class NumArray: def __init__(self, nums): self.prefix [0] for x in nums: self.prefix.append(self.prefix[-1] x) def sumRange(self, l, r): return self.prefix[r 1] - self.prefix[l]这段代码非常短但信息密度很高。self.prefix初始化为一个包含 0 的列表然后逐个追加前缀和sumRange里直接用下标相减。我让集训学员在纸上把这个类的构造过程画一遍尤其是prefix长度和nums长度的关系以及sumRange里下标r 1和l的由来。把这些彻底想明白了一维前缀和就不会再有问题。7.2 第 724 题寻找数组的中心下标这道题表面上是“找中间位置”但本质还是前缀和的应用。题目要求找到一个下标i使得左边所有元素之和等于右边所有元素之和。常规做法是总数减去当前元素再减去左边和得到右边和然后比较。我先算出总和total再从左到右维护左边和left_sum右边和就等于total - left_sum - nums[i]。判断二者相等即可。def pivotIndex(nums): total sum(nums) left_sum 0 for i, x in enumerate(nums): if left_sum total - left_sum - x: return i left_sum x return -1这里虽然没有显式构造前缀和数组但思路完全建立在“两侧和的对比”上属于前缀和思想的灵活应用。很多学员觉得“只有建了数组才叫前缀和”其实不是前缀和更多的是一种累计思考方式。7.3 第 974 题和可被 K 整除的子数组这道题也算“前缀和哈希表”的经典变体。因为同余性质如果两个前缀和对 K 的余数相同那么它们之间的区间和就能被 K 整除。所以在遍历时维护当前cur计算mod cur % K然后在哈希表里查找相同余数出现过的次数。被 5.3 的模板直接扩展一下就行核心代码几乎不变。8. 我在集训中反复踩过的坑——前缀和的 4 个高频错误8.1 下标越界与差一错误前缀和数组比原数组多了一位prefix的最后一格对应的是所有元素之和访问prefix[n]是合法的但如果你把下标搞混很容易访问prefix[n1]或prefix[-1]。这类问题我在给学员改代码时看到最多解决办法就是严格按照“前 k 个元素”的约定写并在测试用例里故意算一个l0、rn-1的全区间和。8.2 循环里更新哈希表的顺序错了如第 5.3 节所说“先查询后更新”是铁律。这个顺序一旦反过来重复统计的问题就会立刻出现而且答案往往差得不多特别难排查。我建议在代码里加个注释把这个顺序写明白防止面试时一紧张就写反。8.3 二维前缀和忘了减 1二维前缀和里matrix[i-1][j-1]的下标问题太容易错了。很多人初学时会写成matrix[i][j]然后发现越界。我自己的习惯是先把pre的大小定为(m1)×(n1)然后在双重循环的第一行写清楚注释“matrix 下标要减 1”每次写代码之前默念一遍。8.4 忘了开 long long 或处理负数取模C 做题时如果题目数据范围大前缀和相加可能溢出int。我通常会直接开vectorlong long省得事后 debug。另外像 LeetCode 974 这种“被 K 整除”的题负数的取模跟 C 的%行为可能和你预期不一致建议用((cur % K) K) % K来规范到非负余数这也是一个常见的隐藏雷点。9. 给不同阶段读者的建议——前缀和怎么练才有效如果是完全没接触过前缀和的新手我建议先不要碰难题老老实实做三件事。第一把一维模板背熟然后在纸上手算一个小数组的前缀和和区间查询验证结果。第二把 LeetCode 303 和 724 独立写出来不要看题解。第三再做几道纯模板题比如 LeetCode 1480“一维数组的动态和”感受一下“累加”到“前缀和”的无缝衔接。如果已经能写模板了就进入第二阶段掌握“前缀和哈希表”的题型。重点做 LeetCode 560、974、525把思路提炼成统一的模式。我个人建议每道题在 AC 之后再想一想如果题目改成“子数组长度至少为 2”“不能包含某个值”等条件代码要怎么改。这个扩展思考能帮你在面试官出变体时不至于当场卡壳。第三阶段就是把前缀和扩展到二维配合矩阵类题目做练习。做了 LeetCode 304 之后可以顺手看看 1074“元素和为目标值的子矩阵数量”那道题需要把二维问题按行压缩成一维再用哈希表优化是二维前缀和和“前缀和哈希表”的结合题型。建议在你把前两个阶段都夯实了之后再去碰。10. 关于前缀和我最后想说的几句话我做了这么多年算法相关的学习和带新人越来越觉得前缀和这种基础算法被严重低估了。你说它难吗模板背下来一段代码就能写。但它背后的“预处理空间换时间”的思想是很多高效算法的共同根基。面试官爱考它不是因为题本身有多难而是因为它能快速检验一个人有没有建立“高频查询之前先做预处理”的思维习惯。我个人在实际集训中还有一个体会前缀和这类基础算法最忌讳的是“看懂了、没写熟”。很多学员看一遍题解觉得会了结果两天后连模板都敲不利索。所以我会建议他们把它当成键盘肌肉记忆的一部分写到不用过脑子就能输出正确模板的程度。等到后面学差分、树状数组、线段树时你会发现前期这个熟练度带来的收益非常明显。最后分享一个我自己实践过的小技巧每学一个新算法就把它和已经学过的算法对比一下找出联系和区别。前缀和、差分、滑动窗口三兄弟经常出现在同一套题里你如果能在做题时主动判断“这题该用哪个”进步会快很多。希望这篇总结对你有帮助也欢迎你带着自己的实战问题来找我聊。
