文章目录题目解析为什么这道题值得你花几分钟看完暴力解法为什么可以用前缀和前缀和原理与两种实现方法方法一前缀和数组包含当前下标dp[i] nums[0]~nums[i] 的和方法二前缀和后缀和均不包含当前下标关键设计逻辑代码实现方法一前缀和数组包含当前下标方法二前缀和后缀和不包含当前下标细节总结下题预告题目解析题目链接力扣 724.寻找数组的中心下标题目描述示例 1输入nums [1, 7, 3, 6, 5, 6]输出3解释中心下标是 3 。左侧数之和 sum nums[0] nums[1] nums[2] 1 7 3 11 右侧数之和 sum nums[4] nums[5] 5 6 11 二者相等。示例 2输入nums [1, 2, 3]输出-1解释数组中不存在满足此条件的中心下标。示例 3输入nums [2, 1, -1]输出0解释中心下标是 0 。左侧数之和 sum 0 下标 0 左侧不存在元素右侧数之和 sum nums[1] nums[2] 1 -1 0 。提示1 nums.length 104-1000 nums[i] 1000为什么这道题值得你花几分钟看完这道题是“前缀和”算法的经典入门题核心价值在于暴露暴力解法的局限性让你直观感受O(n²)算法在数据量增大时的低效理解优化的必要性强化前缀和的核心思想前缀和的本质是“预计算区间和减少重复计算”这道题的场景多次查询不同区间和完美契合前缀和的应用条件衔接更复杂的算法掌握本题的前缀和思路后能轻松迁移到二维前缀和、子数组和问题如力扣 560. 和为 K 的子数组等更难的题目, 同时前缀和的理解也是对动态规划的一个铺垫是算法学习的“关键一步”。暴力解法暴力解法思路暴力解法的核心是“遍历每个下标逐个计算左右区间和”具体步骤如下用变量i遍历数组的每个下标从0到nums.length-1对每个i分别计算左侧和0 ~ i-1元素之和和右侧和i1 ~ nums.length-1元素之和若左侧和等于右侧和直接返回i因要求“最靠左”首次满足即答案若遍历结束无满足条件的i返回-1。暴力解法的思路就是用一个变量 (i) 来遍历整个数组每当遍历到一个点的时候将前半部分 (0 ~ i-1) 和 后半部分 (i1 ~ n-1) 的结果遍历相加出来最后对比左半部分与右半部分的值。时间复杂度太高暴力解法的时间复杂度是O(n²)遍历每个下标需要O(n)次操作对每个下标计算左右和时又需要分别遍历O(n)个元素。虽然本题数据范围n ≤ 10⁴下10⁸次操作能“侥幸通过”但如果数据量扩大到n 10⁵10¹⁰次操作会远超计算机每秒约10⁸次的处理能力必然超时。这说明当需要多次计算区间和时“每次重新遍历”的暴力思路不可持续必须寻找更优的预计算方案。为什么可以用前缀和我们思考为什么暴力算法会超时核心是解决“重复计算区间和”的问题——而前缀和正是为此设计的“预计算工具”。我们先明确前缀和的适用条件再看本题是否契合前缀和的适用场景前缀和数组的核心价值是将“区间和的计算”从O(n)优化到O(1)其适用场景需满足两个条件需多次查询区间和若仅需计算一次区间和前缀和的“预计算”反而会多花时间但多次查询时预计算的成本能被后续的快速查询抵消。数组元素静态不变前缀和是基于原始数组计算的若数组元素有动态修改如插入、删除、更新前缀和数组需重新计算失去优势此时需用线段树等结构。本题与前缀和的契合度多次查询区间和本题对每个下标i都要查询两个区间和左侧0~i-1、右侧i1~n-1共需查询2n次区间和完全符合“多次查询”的场景数组静态无修改题目给定的nums是静态数组无任何动态操作前缀和数组计算一次后可反复使用。在我的前两篇博客中我们从一维和二维的两个层次分别详细的讲解了什么是前缀和如何应用感兴趣的朋友可以去看一看一维前缀和模板 二维前缀和模板因此用前缀和优化本题是“最优解”能将时间复杂度从O(n²)降至O(n)预计算前缀和O(n)遍历查询O(n)。前缀和原理与两种实现方法前缀和的核心是“用一个数组存储前k个元素的和”但根据“是否包含当前下标”的定义可衍生出两种实现方法分别对应不同的边界处理逻辑。方法一是在第一次上手的时候因为有前面两道题的铺垫惯性思维想出来的好处是只建立了一个前缀和数组但是缺点是要进行边界处理方法二则是用两个前缀和数组准确地说是一个前缀和一个后缀和可以巧妙地避免我方法一的边界问题。方法一前缀和数组包含当前下标dp[i] nums[0]~nums[i]的和1. 前缀和数组定义设dp为前缀和数组dp[i]表示从nums[0]到nums[i]的所有元素之和递推公式为初始值dp[0] nums[0]只有第一个元素递推式dp[i] dp[i-1] nums[i]第i个元素的和 前i-1个元素的和 当前元素。2. 左右和的计算逻辑对任意下标i我们需要计算左侧和0 ~ i-1的和。若i0最左端左侧无元素和为0否则为dp[i-1]。右侧和i1 ~ n-1的和。若i n-1最右端右侧无元素和为0否则为dp[n-1] - dp[i]整个数组的和 - 前i个元素的和即i右侧的和。3. 边界处理细节当i0时只需判断右侧和是否为0即dp[n-1] - dp[0] 0当i n-1时只需判断左侧和是否为0即dp[i-1] 0当0 i n-1时判断dp[i-1] (dp[n-1] - dp[i])可简化为dp[n-1] dp[i] dp[i-1]左右和相等时总和 左侧和 当前元素 右侧和 左侧和 当前元素 左侧和 2*左侧和 当前元素 dp[i] dp[i-1]。方法二前缀和后缀和均不包含当前下标1.公式推导两个数组的递推公式不是凭空来的而是基于“范围连续性”推导得出我们分别拆解前缀和数组f的递推从左往右算目标计算每个f[i]0~i-1的和观察相邻下标的关系当i0时左侧无元素f[0] 0初始值无需计算当i1时f[1]是0~0的和即nums[0]而f[0] 0所以f[1] f[0] nums[0]当i2时f[2]是0~1的和即nums[0]nums[1]而f[1] nums[0]所以f[2] f[1] nums[1]以此类推当i 1时f[i]的范围0~i-1f[i-1]的范围0~i-2 新增元素nums[i-1]。最终得出f的递推公式 f[i] f[i-1] nums[i-1]适用于i从1到n-1后缀和数组g的递推从右往左算目标计算每个g[i]i1~n-1的和观察相邻下标的关系当in-1时右侧无元素g[n-1] 0初始值无需计算当in-2时g[n-2]是n-1~n-1的和即nums[n-1]而g[n-1] 0所以g[n-2] g[n-1] nums[n-1]当in-3时g[n-3]是n-2~n-1的和即nums[n-2]nums[n-1]而g[n-2] nums[n-1]所以g[n-3] g[n-2] nums[n-2]以此类推当i n-2时g[i]的范围i1~n-1g[i1]的范围i2~n-1 新增元素nums[i1]。最终得出g的递推公式 g[i] g[i1] nums[i1]适用于i从n-2到02.使用前缀和数组通过变量i遍历数组元素逐一判断是否即判断f[i] g[i]即可3、核心定义为什么“不包含当前下标”能避边界先明确两个数组的核心作用——为每个下标i提供“无需修改的左右和计算方式”关键在于“范围定义”的设计数组核心定义覆盖元素范围作用前缀和数组ff[i]代表「下标i左侧所有元素的和」从nums[0]到nums[i-1]不包含i直接作为i的左侧和无需额外调整后缀和数组gg[i]代表「下标i右侧所有元素的和」从nums[i1]到nums[n-1]不包含i直接作为i的右侧和无需额外调整关键设计逻辑当i在数组两端时“不包含当前下标”的定义会自然让“无元素的一侧和为 0”当i0最左端左侧没有元素f[0]覆盖nums[0-1]不存在的范围自然为 0当in-1最右端右侧没有元素g[n-1]覆盖nums[n]不存在的范围自然为 0。这就避免了方法一中“单独判断i0或in-1”的麻烦所有下标i都能复用同一套“f[i] g[i]”的判断逻辑。代码实现方法一前缀和数组包含当前下标#includevectorusingnamespacestd;classSolution{public:intpivotIndex(vectorintnums){intnnums.size();// 处理数组长度为1的特殊情况此时中心下标必为0因左右和均为0if(n1)return0;// 1. 构建前缀和数组 dpvectorintdp(n,0);dp[0]nums[0];for(inti1;in;i){dp[i]dp[i-1]nums[i];}// 2. 遍历每个下标判断左右和是否相等for(inti0;in;i){if(i0){// 左和为0判断右和是否为0if(dp[n-1]-dp[0]0){return0;}}elseif(in-1){// 右和为0判断左和是否为0if(dp[i-1]0){returnn-1;}}else{// 中间下标左和 dp[i-1]右和 dp[n-1] - dp[i]if(dp[i-1](dp[n-1]-dp[i])){returni;}}}// 无满足条件的下标return-1;}};方法二前缀和后缀和不包含当前下标#includevectorusingnamespacestd;classSolution{public:intpivotIndex(vectorintnums){intnnums.size();vectorintf(n,0);// f[i]i左侧所有元素的和0~i-1vectorintg(n,0);// g[i]i右侧所有元素的和i1~n-1// 1. 计算前缀和数组 ffor(inti1;in;i){f[i]f[i-1]nums[i-1];}// 2. 计算后缀和数组 g从后往前递推for(intin-2;i0;i--){g[i]g[i1]nums[i1];}// 3. 遍历判断左右和相等即返回for(inti0;in;i){if(f[i]g[i]){returni;}}// 无满足条件的下标return-1;}};细节总结时间与空间复杂度两种方法的时间复杂度均为O(n)两次遍历数组空间复杂度均为O(n)存储前缀和/后缀和数组。若想进一步优化空间可将前缀和用变量实时计算无需数组但数组实现更直观适合入门理解。边界处理的关键方法一的核心是“单独判断两端下标”方法二的核心是“让数组定义天然覆盖边界”两种思路无优劣之分可根据个人习惯选择。“最靠左”的隐含条件因遍历顺序是从左到右首次满足条件的下标即为“最靠左”的答案无需额外处理。下题预告掌握了“前缀和预计算区间和”的思路后我们将迎来一道进阶题——力扣 238. 除自身以外数组的乘积。这道题的核心场景是“计算每个元素除自身外所有元素的乘积”且要求时间复杂度O(n)、空间复杂度O(1)除输出数组外。它将前缀和的“预计算”思路延伸到“前缀积”与“后缀积”进一步强化“减少重复计算”的优化思维同时加入空间优化的挑战是前缀和思想的绝佳拓展练习。“Doro又又又带着小花来啦奖励看到这里的你如果觉得这篇拆解帮你理清了双前缀和数组的脉络摆脱了暴力解法超时的困扰别忘了点赞收藏呀下次写前缀和题想不起来查询公式怎么用、边界怎么处理时翻到这篇就能快速回忆关键细节关注博主后面还会一起攻克更多前缀和进阶题、差分相关题型比如下一篇要讲的‘前缀和结合差分处理矩阵更新’从‘会用模板’到‘灵活变形’Doro也会和你一起跟着这个博主一步一步扎实进阶”
