★ FEATURED ARTICLE 任何一个在数组、区间问题上卡壳过的人迟早都会遇到“前缀和”这个名字。我最早刷题时觉得它无非就是预处理一个累加数组后来才发现这一招能串起大量子数组、矩阵、连续序列问题。如果你刚接触算法刷题或者被“区间求和”“子数组计数”这类题目绕晕这篇内容就是把前缀和从原理到套路完整拆给你看。先一句话说清楚前缀和是什么用一个额外数组把原数组从开头到当前位置的累计和存下来。有了这个累计数组任意连续区间的和就能用两个前缀和相减得到查询时间从O(n)降到O(1)。听起来简单但它真正的威力在于配合哈希表、余数、二维矩阵、差分数组能解决一大批看似不相关的题目。这篇会从原理讲到实操再讲讲那些不踩一次就记不住的坑适合刚入门数组题的读者也适合准备面试想快速建立题型体系的人。1. 前缀和到底在解决什么问题1.1 从“区间求和”说起给定一个数组比如[3, 1, 4, 1, 5, 9, 2, 6]让你频繁求某个子区间[l, r]的和你会怎么做最朴素的办法是每次从l遍历到r把元素加起来。如果只查一次没问题。但如果查询次数很多比如一万次、十万次每次都重新遍历时间复杂度就变成 O(n * q)很容易超时。前缀和的思路很简单预先把每个位置之前的累计和都算出来。设pre[i]表示nums[0]到nums[i-1]的和也可以定义为到nums[i]不同写法而已那么区间[l, r]的和就等于pre[r1] - pre[l]。为什么因为pre[r1]包含了从开头到r的所有元素pre[l]只包含开头到l-1的元素两者相减正好剩下l到r这一段的和。整个过程只做一次减法跟区间长度无关。这个思想看起来单调但它是很多复杂题目的底层构件。你不需要每次现算而是提前“记账”用账本上的两个数字相减得出任意一段的差额。这就是前缀和的核心价值把区间查询的时间复杂度从 O(n) 降为 O(1)代价只是预处理时的 O(n) 空间和时间。1.2 为什么要用前缀和而不是每次遍历有人会问预处理也要花 O(n) 时间如果只查一两次没必要啊。但实际刷题场景里题目要么是“多次查询”要么是“求所有满足条件的子数组个数”这两种情况暴力都会变得很昂贵。拿“多次查询区间和”举例数组长度 n 10^5查询次数 q 10^5暴力就是 10^10 次加法基本不可能通过。用前缀和预处理 10^5 次之后每次查询 O(1)总共 10^5 10^5 次轻松过。这是“离线计算 快速查询”的经典思路和缓存一个道理。再看子数组类问题比如“有多少个子数组的和等于 k”。暴力枚举所有子数组需要 O(n^2)用前缀和后可以转换成“前缀和之间的差”再配合哈希表进一步优化到 O(n)。这时前缀和不仅仅是加速查询的工具它把原问题转化为“两个前缀和之间的关系”这是质的改变。所以我习惯把前缀和看成一种“数据预处理思维”当你要反复使用某个数据片段的汇总信息时就先把它全部算好存起来后面直接查。数组区间求和是最直观的应用但延伸出去前缀积、前缀异或、前缀状态都能用同一套思想。1.3 两个版本的前缀和定义边界线关于pre[i]的定义刷题网站上能看到两种主流写法搞混很容易出错。第一种pre[i]表示nums[0]到nums[i]的和。那么区间[l, r]的和是pre[r] - (l 0 ? pre[l-1] : 0)。这种写法需要处理l-1越界的情况通常会在外面包一层判断或者把数组后移。第二种pre[i]表示nums[0]到nums[i-1]的和pre[0] 0pre[1] nums[0]以此类推。区间[l, r]的和就是pre[r1] - pre[l]完全不需要处理l0的边界因为pre[0]已经存在了。这是我最喜欢的写法也是大多数题解默认的写法。代码如下n len(nums) pre [0] * (n 1) for i in range(n): pre[i 1] pre[i] nums[i] # 区间 [l, r] 的和闭区间 sum_lr pre[r 1] - pre[l]为什么要多开一位核心原因是让pre[0]代表“空区间”的和避免l - 1出现负数索引。所有从数组开头开始的区间都能统一用pre[r1] - pre[0]表示。这个细节看起来小但在后面配合哈希表时特别重要哈希表里的初始键0: 1就是从这里来的。2. 高频场景与变体2.1 子数组和等于目标值这是前缀和最经典的变体也是面试常客给定整数数组nums和一个整数k返回连续子数组中和等于k的个数。暴力枚举要两重循环O(n^2)。用前缀和的话设子数组nums[j1..i]的和为pre[i1] - pre[j]如果等于k说明pre[j] pre[i1] - k。问题变成了遍历每个前缀和cur看看之前出现过多少个cur - k。用哈希表记录每个前缀和出现的次数就能在一次遍历内完成任务。这背后的思想很简单每到一个新位置我不关心前面所有前缀和具体存在哪里只关心等于某个值的有多少个。哈希表正好能做这种统计。这种“把两层循环中内层条件改写成哈希查询”的技巧是很多进阶题的核心。2.2 二维前缀和矩阵区域求和前缀和从一维升到二维用于快速求矩阵中任意子矩阵的元素和。设sum[i][j]表示矩阵中从(0,0)到(i-1,j-1)围成区域的元素和。推导公式用的是容斥原理sum[i][j] sum[i-1][j] sum[i][j-1] - sum[i-1][j-1] matrix[i-1][j-1]查询子矩阵(r1, c1)到(r2, c2)的和时area sum[r21][c21] - sum[r1][c21] - sum[r21][c1] sum[r1][c1]减的部分多减了一次左上角区域所以要加回来。这个公式初看容易记反但验证一下小的 2x2 矩阵就能明白。二维前缀和用于“矩阵区域和”类题目以及后续的“最大子矩阵和”问题都是一把利器。2.3 前缀和配合哈希表的“差值思想”一维前缀和配上哈希表能解决的不只是“和等于 k”还有“和能被 k 整除”“和为奇数/偶数”“和为某个区间范围”等一整套问题。核心套路是对当前前缀和cur想在之前的前缀和中找到满足某种关系的prev。如果条件是“差值固定”那就用cur - target如果条件是“余数相同”那就用cur % k如果条件是“状态相同”那就用一个二进制位表示状态。总之哈希表里存的东西可以灵活变化存次数、存最早位置、存最晚位置、存布尔值。前缀和负责提取区间信息哈希表负责快速查找历史。2.4 差分数组与前缀和的“互逆”差分数组可以看成前缀和的逆运算原数组是前缀和数组则差分数组就是原数组相邻元素之差。如果要给原数组的多个区间统一加一个值用差分数组可以在 O(1) 时间内更新每个区间的端点最后再用前缀和还原。举例先对diff[l] val、diff[r1] - val所有修改完成后对diff做一次前缀和得到的就是最终数组。这个技巧在“航班预订”“区间覆盖”等问题里经常出现。虽然差分数组不是前缀和的直接同族但它们属于同一个“预处理 累减/累加”的框架放在一起理解更容易形成体系。3. 刷题实操三道典型题目从暴力到优化3.1 和为 K 的子数组哈希表解法先看一道最经典的题给定数组求和为k的连续子数组的个数。比如nums [1, 1, 1]k 2结果是 2[1,1]有两个区间。暴力写法是枚举左右端点两层循环。但用前缀和加哈希表可以做到一次遍历def subarraySum(nums, k): prefix_sum_count {0: 1} current_sum 0 result 0 for num in nums: current_sum num result prefix_sum_count.get(current_sum - k, 0) prefix_sum_count[current_sum] prefix_sum_count.get(current_sum, 0) 1 return result重点在于{0: 1}的初始化。为什么必须有 0因为current_sum - k 0时表示从头开始的子数组已经满足和等于k。如果不初始化 0这类子数组会被漏掉。另一个重点更新哈希表要在累加result之后。如果先更新当前前缀和再查询会把自己当成历史前缀导致区间长度为 0 的情况被计入结果错误。顺序不能反。3.2 二维区域和检索矩阵自动求和题目是给定一个二维矩阵反复查询子矩阵元素和。直接每次遍历会超时用二维前缀和预处理后就很快。以 Python 为例构建二维前缀和class NumMatrix: def __init__(self, matrix): m, n len(matrix), len(matrix[0]) if matrix else 0 self.sum [[0] * (n 1) for _ in range(m 1)] for i in range(m): for j in range(n): self.sum[i 1][j 1] ( self.sum[i][j 1] self.sum[i 1][j] - self.sum[i][j] matrix[i][j] ) def sumRegion(self, row1, col1, row2, col2): return ( self.sum[row2 1][col2 1] - self.sum[row1][col2 1] - self.sum[row2 1][col1] self.sum[row1][col1] )注意二维前缀和矩阵的行列都比原矩阵大 1所有下标都对应到1后。查询公式里四个坐标不能写错总块减上边条减左边条加回调减重的左上角。我刷这种题时经常先在纸上画一个 2x3 的格子手动算一遍再套代码印象会深刻很多。3.3 连续子数组和整除问题这道题和“子数组和等于 k”不太一样它要求判断是否存在长度至少为 2 的连续子数组其和为k的倍数k是正整数。数学原理是如果两个前缀和pre[i]和pre[j]对k取模结果相同那么pre[i] - pre[j]能被k整除也就是nums[j..i-1]这段子数组的和是k的倍数。因此只需要遍历前缀和用一个哈希表记录“某个余数最早出现的位置”当遇到相同余数时检查当前位置和最早位置的距离是否大于等于 2。def checkSubarraySum(nums, k): mod_seen {0: -1} current_sum 0 for i, num in enumerate(nums): current_sum num mod current_sum % k if mod in mod_seen: if i - mod_seen[mod] 2: return True else: mod_seen[mod] i return False这里存的是最早位置i而不是次数因为我们关心的是最长距离是否满足长度条件。为什么初始化{0: -1}因为前缀和为 0 时相当于从数组开头之前开始这样当某个位置取模为 0 时长度计算就不会漏掉从 0 到当前位的完整数组。4. 前缀和题型的进阶套路4.1 前缀和 哈希表模式识别这类题目并不难识别我总结了一个固定模板# 初始化哈希表通常有初始键 hash_table defaultdict(...) hash_table[initial_state] initial_value prefix_sum 0 for i in range(n): prefix_sum nums[i] # 根据题意查询前缀和 answer hash_table.get(prefix_sum - target, 0) # 更新哈希表记录当前前缀和的相关信息 hash_table[prefix_sum] ...核心是明确四件事当前前缀和是什么当前要满足的条件对应到历史前缀和上是什么值要统计的是次数、最早位置还是其他信息更新哈希表的时机是查询前还是查询后。一旦这四件事想清楚题目基本就解出来了。和“两数之和”的哈希表思路一样前缀和哈希表也算一种“先查后存”的模板。4.2 前缀和 取模/余数当题目里出现“可以被 k 整除”“是 k 的倍数”这些关键词就可以往取模方向想。两个前缀和对 k 取余相同中间那段的和就是 k 的倍数。这时哈希表里存储的是余数而不是前缀和本身。注意有些题目要求区间长度至少为 2有些没有这个要求处理方式不同。没有长度要求时只需要记录余数出现次数有长度要求时记录最早出现位置并通过当前位置与最早位置之差判断长度。还有一类变体是“前缀和除以 k 的余数落在某个区间内”这时哈希表可能要为每个余数维护一个有序列表或者改用平衡树之类的结构。这类题目就属于中等偏上了。4.3 前缀和与奇偶/状态压缩有些题目里的“前缀”并不一定是数值和而是一种状态。比如求“含有偶数个某个字符的最长子串”可以用一个二进制位来压缩状态从开头到当前位置的状态作为前缀状态。两个位置的状态相同说明中间这段字符的出现次数奇偶性完全相同再按需判断。这类题虽然不叫前缀和但本质是同一套思维把从起点到当前位置的累计信息不是和是状态作为 key通过查询历史相同状态来计算答案。状态压缩只是把多个维度的信息编码成了一个整数便于哈希。熟悉了这种抽象你会发现前缀和真正厉害的地方不是“求和”本身而是“累计信息”这个思想。累计的是数字、是余数、是状态、是异或结果都行。5. 常见坑与排查技巧实录5.1 前缀和数组长度到底开多少一维前缀和我建议统一开n 1而不是n。如果开n查询前缀和pre[r1]时可能越界需要额外判断。多开一位后pre[0] 0作为哨兵所有边界情况都统一处理。二维同理(m 1) x (n 1)。我见过不少同学因为少开一位导致i-1或j-1访问负索引报错后还半天找不到原因。这是最高频的坑。5.2 哈希表初始化为什么要有 0在“和为 k 的子数组”这道题里如果不初始化{0: 1}所有从头开始且和为 k 的子数组都不会被统计到。因为current_sum - k 0时查询hash_table[0]会得到默认值 0。同理“连续子数组和”题目里初始化{0: -1}是为了让从开始位置算起的区间也有对应的“位置”可以比较长度。记住一个原则如果答案依赖于“从原数组开头开始的区间”哈希表里就必须有初始状态。5.3 二维前缀和的边界公式别背错二维前缀和查询公式是四个坐标很容易在笔试时紧张写错。我的记忆方法是整体 - 上边块 - 左边块 被重复减掉的左上角对应到公式就是sum[r21][c21]是整个大块sum[r1][c21]是上边部分sum[r21][c1]是左边部分sum[r1][c1]是重叠的左上角。构建公式的记忆方法是当前位置的总和等于“左上角区域 上面一行 左面一列 - 重复的左上角 当前格子”。写成代码就是三个/-的循环。5.4 取模负数和 Integer 溢出的处理前缀和累加很容易超过 32 位整数范围尤其nums[i]也可能是负数。在 Java 等语言里累加值最好用long类型。Python 没有这个问题但也要注意性能。负数取模是另一个坑。比如-5 % 3在 Python 里结果是 1而在某些语言里结果是 -2。如果你写的语言对负数取模处理不同要统一转成非负数mod ((cur % k) k) % k。保证余数在[0, k-1]区间才能正确比较。还有一种情况在统计子数组和为 k 时如果k可以为负数target current_sum - k只是普通整数哈希表不受影响但k为 0 时要小心相当于查找当前前缀和本身意味着存在和为 0 的区间。逻辑上没问题但容易忽略。6. 刷题节奏与进阶建议6.1 入门期先掌握一维和二维模板如果你刚开始刷前缀和不要急着做太多变体。先把一维前缀和数组写熟练从“存在重复元素区间求和”“子数组和等于指定值”这类题开始。要求自己不看题解写出来并理解pre[0]的作用。然后做二维区域和把构建和查询的公式背下来再通过手写小矩阵验证。一维和二维各做 3-5 道题应该就能形成肌肉记忆。此时可以接触差分数组感受“原数组 - 差分 - 前缀和还原”的流程。6.2 中期从“求和”到“条件”的转换当你能熟练套用前缀和模板后开始挑战带条件的题目。比如“和为 k 的子数组”“和可被 k 整除的子数组”“最长奇偶状态相同的子串”。每做一类题在笔记里写清楚三件事当前前缀和的定义、哈希表的 key 是什么、value 是什么。这个阶段的目标不是刷题数量而是分类归纳。我会把前缀和题目分成三类“固定差值型”“取模余数型”“状态压缩型”。不同的类型对应不同的查询方式一开始可能反应不过来但归纳多了看到题目里的“连续子数组”和“若干次查询”就会下意识想到前缀和。6.3 后期建立题型反应链后期刷题更重要的是把前缀和同其他算法结合起来。比如“前缀和 二分”解决最小子数组长度问题“前缀和 单调栈”解决柱状图问题“前缀和 动态规划”解决子矩阵最大值问题。这时候前缀和不再是一个专题而是一个基础工具需要你看到题目时自动判断是否值得用它。我的建议是建立一个自己的“索引表”遇到nums[i]、连续、区间、子数组、矩阵区域这些关键词先把前缀和列到候选方案里再通过题目具体条件决定是否需要哈希表、差分或取模。这个过程看起来很自然但需要一定的题量支撑。还有个小技巧多关注“前缀和数组本身还能怎么用”。比如前缀和数组是否单调如果原数组全非负前缀和单调递增就能配合二分查找。这个衍生价值很容易被忽略但面试时如果能让面试官看到这种反应印象分会高很多。我个人刷前缀和的体会是它不像动态规划那样需要很强的抽象能力也不像图论那样需要复杂的模型它更像一个“账本思维”——先把累计信息记清楚任何区间问题都能从账本里查询。最大的门槛反而不是原理而是边界处理和哈希表初始化这些细节。踩过几次坑后你会发现这些坑都是固定的、可规避的。所以读代码时多问一句“为什么这里要初始化 0”多比划一下二维前缀和的加法减法比盲目刷一百道题更有效。最后再分享一个小技巧每次做完一道前缀和题试着把题目改一改再重做一遍。比如把“和为 k”改成“和小于 k 的最长区间”把“一维数组”改成“矩阵前缀和”把“子数组”改成“子序列问题能不能用”这样改动一次你对这个思想的理解就会深一层。前缀和的价值就在这些反复拆解和重构里被真正榨出来。
阅读完成 · 觉得有帮助？
