从入门到精通：前缀和算法全解析，5道经典题吃透核心思想

从入门到精通前缀和算法全解析5道经典题吃透核心思想前缀和Prefix Sum是算法领域中最基础、最实用、面试最高频的技巧之一。它的核心思想极其简单用空间换时间将区间和的查询从 O(n) 优化到 O(1)。但很多人只停留在「一维前缀和求区间和」的表层对二维前缀和、前缀和的变种应用、与哈希表的结合一知半解。今天我们就通过5道经典题目从一维到二维从基础到进阶彻底吃透前缀和算法。文章目录从入门到精通前缀和算法全解析5道经典题吃透核心思想一、先搞懂前缀和的核心原理1. 什么是前缀和2. 为什么要用前缀和二、基础篇一维前缀和模板题题目DP34【模板】前缀和题目描述思路分析代码实现逐行注释关键细节拆解三、进阶篇二维前缀和矩阵区间和题目DP35【模板】二维前缀和题目描述思路分析代码实现逐行注释关键细节拆解四、应用篇1寻找数组的中心下标LeetCode 724题目描述思路分析代码实现逐行注释优化版空间O(1)五、应用篇2除自身以外数组的乘积LeetCode 238题目描述思路分析代码实现逐行注释优化版空间O(1)六、高阶篇前缀和 哈希表和为K的子数组 LeetCode 560题目描述思路分析代码实现逐行注释关键细节拆解七、前缀和算法总结与选型指南1. 核心公式速查表2. 避坑指南3. 拓展应用八、写在最后一、先搞懂前缀和的核心原理1. 什么是前缀和对于一个数组a[1..n]我们定义前缀和数组s[0..n]其中s[0] 0s[i] a[1] a[2] ... a[i]这样一来任意区间[l, r]的和就可以用s[r] - s[l-1]直接算出时间复杂度从 O(n) 降到 O(1)。2. 为什么要用前缀和时间复杂度优化预处理 O(n)每次查询 O(1)适合多次区间查询的场景空间复杂度极低仅需额外 O(n) 空间几乎无负担扩展性极强可拓展到二维、多维可结合哈希表、双指针等多种算法二、基础篇一维前缀和模板题题目DP34【模板】前缀和题目描述给定长度为n的数组a[1..n]有m次查询每次给出l, r输出区间[l, r]的元素和。思路分析这是前缀和的最基础模板题核心就是构建前缀和数组然后用s[r] - s[l-1]计算区间和。代码实现逐行注释#includeiostream#includevectorusingnamespacestd;intmain(){// 读入数组长度n和查询次数qintn,q;cinnq;// 原数组下标从1开始方便前缀和计算s[0]0vectorintarr(n1);for(inti1;in;i){cinarr[i];}// 前缀和数组用long long避免溢出元素可到1e9n到1e5总和超intvectorlonglongdp(n1);for(inti1;in;i){// 递推公式s[i] s[i-1] a[i]dp[i]dp[i-1]arr[i];}intl0,r0;while(q--){cinlr;// 区间和公式s[r] - s[l-1]coutdp[r]-dp[l-1]endl;}return0;}关键细节拆解下标从1开始为了让s[0] 0处理l1时s[l-1] s[0] 0的边界情况代码更简洁用long long存前缀和当数组元素为1e9、长度为1e5时总和为1e14远超int的最大值约2e9必须用long long避免溢出时间复杂度预处理 O(n)每次查询 O(1)总复杂度 O(nq)完美应对大数据量三、进阶篇二维前缀和矩阵区间和题目DP35【模板】二维前缀和题目描述给定n×m的矩阵a有q次查询每次给出左上角(x1,y1)和右下角(x2,y2)输出该子矩阵的元素和。思路分析二维前缀和的核心是容斥原理。我们定义前缀和矩阵s[i][j]表示从(1,1)到(i,j)的所有元素之和。递推公式s[i][j] a[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1]当前元素 上方前缀和 左方前缀和 - 重复计算的左上角前缀和子矩阵和公式sum s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1]右下角前缀和 - 上方多余部分 - 左方多余部分 重复减去的左上角部分代码实现逐行注释#includeiostream#includevectorusingnamespacestd;intmain(){intn0,m0,q0;cinnmq;// 原矩阵下标从1开始vectorvectorintarr(n1,vectorint(m1));for(inti1;in;i){for(intj1;jm;j){cinarr[i][j];}}// 二维前缀和矩阵用long long避免溢出vectorvectorlonglongdp(n1,vectorlonglong(m1));for(inti1;in;i){for(intj1;jm;j){// 二维前缀和递推公式容斥原理dp[i][j]dp[i-1][j]dp[i][j-1]arr[i][j]-dp[i-1][j-1];}}intx10,x20,y10,y20;while(q--){cinx1y1x2y2;// 子矩阵和公式容斥原理coutdp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]dp[x1-1][y1-1]endl;}return0;}关键细节拆解容斥原理是核心二维前缀和的递推和查询本质都是用「加加减减」消除重复计算的部分下标从1开始的重要性同样是为了处理边界比如x11时s[x1-1][y2] s[0][y2] 0无需额外判断时间复杂度预处理 O(n×m)每次查询 O(1)总复杂度 O(n×m q)四、应用篇1寻找数组的中心下标LeetCode 724题目描述给你一个整数数组nums请计算数组的中心下标。数组中心下标是数组的一个下标其左侧所有元素相加的和等于右侧所有元素相加的和。如果中心下标位于数组最左端那么左侧数之和视为0如果位于最右端右侧数之和视为0。如果有多个中心下标返回最靠近左边的那一个如果不存在返回-1。思路分析这是一维前缀和的经典应用先计算数组的总和total遍历数组维护左侧前缀和left_sum对于每个下标i右侧和 total - left_sum - nums[i]如果left_sum 右侧和则i是中心下标否则left_sum nums[i]继续遍历代码实现逐行注释classSolution{public:intpivotIndex(vectorintnums){intnnums.size();// 前缀和数组f[i] 表示 nums[0..i-1] 的和左侧和vectorintf(n),g(n);// 计算左侧前缀和for(inti1;in;i){f[i]f[i-1]nums[i-1];}// 计算右侧前缀和g[i] 表示 nums[i1..n-1] 的和右侧和for(intin-2;i0;i--){g[i]g[i1]nums[i1];}// 遍历找第一个左侧和等于右侧和的下标for(inti0;in;i){if(f[i]g[i]){returni;}}// 不存在中心下标return-1;}};优化版空间O(1)classSolution{public:intpivotIndex(vectorintnums){// 计算数组总和inttotalaccumulate(nums.begin(),nums.end(),0);intleft_sum0;for(inti0;inums.size();i){// 右侧和 总和 - 左侧和 - 当前元素if(left_sumtotal-left_sum-nums[i]){returni;}left_sumnums[i];}return-1;}};五、应用篇2除自身以外数组的乘积LeetCode 238题目描述给你一个整数数组nums返回数组answer其中answer[i]等于nums中除了nums[i]之外其余各元素的乘积。要求不使用除法且在 O(n) 时间复杂度内完成。思路分析这是前缀积 后缀积的经典应用本质是前缀和思想的变种定义前缀积数组ff[i]表示nums[0..i-1]的乘积定义后缀积数组gg[i]表示nums[i1..n-1]的乘积最终answer[i] f[i] * g[i]代码实现逐行注释classSolution{public:vectorintproductExceptSelf(vectorintnums){intnnums.size();// 前缀积数组f[i] nums[0] * nums[1] * ... * nums[i-1]vectorintf(n),g(n);// 初始化边界f[0] 10号元素左侧无元素乘积为1f[0]g[n-1]1;// 计算前缀积for(inti1;in;i){f[i]f[i-1]*nums[i-1];}// 计算后缀积for(intin-2;i0;i--){g[i]g[i1]*nums[i1];}vectorintret(n);for(inti0;in;i){// 答案 前缀积 * 后缀积ret[i]f[i]*g[i];}returnret;}};优化版空间O(1)classSolution{public:vectorintproductExceptSelf(vectorintnums){intnnums.size();vectorintret(n,1);// 先算前缀积存入retintprefix1;for(inti0;in;i){ret[i]*prefix;prefix*nums[i];}// 再算后缀积乘入retintsuffix1;for(intin-1;i0;i--){ret[i]*suffix;suffix*nums[i];}returnret;}};六、高阶篇前缀和 哈希表和为K的子数组 LeetCode 560题目描述给你一个整数数组nums和一个整数k请你统计并返回该数组中和为k的子数组的个数。子数组是数组中元素的连续非空序列。思路分析这是前缀和的高阶应用核心是前缀和 哈希表定义前缀和数组ss[i]表示nums[0..i-1]的和对于子数组[j1, i]其和为s[i] - s[j] k→s[j] s[i] - k我们用哈希表统计前缀和s[j]出现的次数遍历到i时直接查询哈希表中s[i]-k的次数累加到答案中初始化哈希表{0:1}对应s[0]0的情况代码实现逐行注释classSolution{public:intsubarraySum(vectorintnums,intk){// 哈希表key前缀和value该前缀和出现的次数unordered_mapint,inthash;// 初始化前缀和0出现1次对应s[0]0hash[0]1;intsum0;// 当前前缀和intret0;// 答案for(autox:nums){sumx;// 计算当前前缀和s[i]// 查找有多少个s[j] s[i] - k累加到答案if(hash.count(sum-k))rethash[sum-k];// 将当前前缀和加入哈希表hash[sum];}returnret;}};关键细节拆解为什么用哈希表我们需要快速统计「之前出现过多少个s[j] s[i]-k」哈希表可以 O(1) 完成查询总时间复杂度 O(n)为什么初始化{0:1}当s[i] k时s[i]-k 0对应子数组[0, i]必须初始化这个情况时间复杂度O(n)空间复杂度 O(n)完美应对n2e4的数据量七、前缀和算法总结与选型指南1. 核心公式速查表类型递推公式区间和公式适用场景一维前缀和s[i] s[i-1] a[i]sum[l..r] s[r] - s[l-1]一维数组区间和、中心下标、前缀积二维前缀和s[i][j] a[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1]sum[(x1,y1)..(x2,y2)] s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1]矩阵子矩阵和前缀和 哈希表s[i] s[i-1] a[i]统计s[i]-k出现的次数和为K的子数组、连续子数组和问题2. 避坑指南溢出问题数组元素较大、长度较长时必须用long long存前缀和避免int溢出下标问题尽量从1开始存原数组让s[0]0简化边界处理负数问题前缀和可以为负数哈希表可以正常处理无需额外处理时间复杂度前缀和的核心是「预处理O(n)查询O(1)」永远不要用暴力O(n²)的方法3. 拓展应用前缀和思想可以拓展到多维前缀和三维、四维数组的区间和前缀积/前缀异或除自身乘积、子数组异或和问题滑动窗口 前缀和最长子数组和问题树状数组/线段树动态前缀和支持单点修改、区间查询八、写在最后前缀和是算法的「基本功」看似简单却能衍生出无数经典题目。从一维到二维从基础到高阶核心思想始终是用空间换时间预处理加速查询。掌握了前缀和你就搞定了数组区间和、子数组和、矩阵和等一系列高频面试题为后续学习更复杂的算法如动态规划、树状数组打下坚实基础。算法学习的本质是掌握核心思想然后举一反三。前缀和就是最好的例子。