欢迎阅读 欢迎来到「寻找数组的中心下标」题解之旅本文将带你从找出数组左右两侧重量相等的平衡点这一直观场景出发深入理解前缀和 后缀和的巧妙运用并掌握如何用两个辅助数组记录左右累加来在 O(n) 内定位中心下标。在开始之前建议你先了解题目背景这是 LeetCode 724 题给定整数数组nums中心下标定义为左侧所有元素之和等于右侧所有元素之和的位置两侧都不含该元素本身返回最左侧的中心下标不存在返回-1。本质上问题转化为同时维护每个位置的左右两侧累加和并比较。明确学习目标掌握前缀数组 f 与后缀数组 g 的构建理解f[i]、g[i] 都不包含 nums[i] 本身的语义并熟练处理首尾下标与单元素数组等边界情况。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如nums [1, 7, 3, 6, 5, 6]输出3。本文将从问题转化、左右数组构建、双数组比较、边界防护到代码实现层层递进。即使你对前缀和还不熟悉我们也会从把每个位置左右两侧的账先算好再逐位核对这一直觉出发让你轻松抓住核心思想——左账右账各算一遍相等处即中心。现在让我们一起累计两侧之和找到数组的平衡点吧 ⚖️个人主页愿旖旎专栏传送门算法专栏当前学习内容前缀和一.题目724. 寻找数组的中心下标 - 力扣LeetCode​二、算法分析一、问题分析前置分析题目要求在数组nums中找出中心下标左侧元素和 右侧元素和均不含自身返回最左侧的不存在返回-1。关键约束元素可能为负数中心下标可能是首尾位置一侧和为 0要求最左侧的中心。核心思路暴力做法对每个位置都重新累加左右两侧总代价 O(n²)用前缀数组 f左侧和与后缀数组 g右侧和各预处理一遍比较即得答案总复杂度O(n)。 例子暴力为什么不可行数组[1, 7, 3, 6, 5, 6]检查下标 3 时需累加左侧173与右侧56检查下标 4 时又要重新累加1736与6——每个位置的左右和都从零开始重算重复计算大量重叠区间n 个位置最坏 O(n²)。二、算法策略前缀数组 f 后缀数组 g核心步骤初始化f[0] 0下标 0 左侧无元素、g[n-1] 0下标 n-1 右侧无元素。构建前缀 ff[i] f[i-1] nums[i-1]表示下标 i左侧所有元素之和从左往右。构建后缀 gg[j] g[j1] nums[j1]表示下标 j右侧所有元素之和从右往左。比较定位从左到右找第一个f[i] g[i]的位置返回全不满足返回-1。 示例nums [1, 7, 3, 6, 5, 6]下标 i012345nums[i]173656f[i]左侧和018111722g[i]右侧和2720171160构建时 f 从左往右逐个累加f[3] f[2] nums[2] 8 3 11g 从右往左递推g[3] g[4] nums[4] 6 5 11比较发现i3 时 f[3] g[3] 11返回3左侧173与右侧56均为 11。三、正确性说明简单版本f、g 语义精确f[i] nums[0] ... nums[i-1]递推保证恰好是 i 左侧全部元素之和不含 nums[i]g[i]对称地是右侧全部元素之和递推无误差。比较条件等价中心下标的定义左侧和 右侧和与f[i] g[i]逐字对应等式成立即满足题意不会错判。首尾覆盖完整f[0] 0、g[n-1] 0使下标 0 与 n-1 的空侧正确表示为 0中心在边界时也能命中不漏解。最左侧保证从左到右扫描第一个满足条件的位置即最左侧中心符合题目要求。 例子为什么 f[i] 不含 nums[i] 本身下标 3 处f[3] 11来自173g[3] 11来自56元素6即 nums[3]没有计入任何一侧——中心元素本身不属于左右任何一边这正是题目的定义若误把自身算入比较结果会整体偏移、错失真正的中心。四、实现细节边界防护初始化f、g均开n大小f[0] 0、g[n-1] 0vector 默认也为 0但语义上必须明确。边界防护构建 f 时i从 1 到n-1构建 g 时j从n-2到 0均不越界n 1时 f[0] g[0] 0直接返回 0元素为负时 f、g 可能为负不影响比较。复杂度时间 O(n)两次构建 一次比较空间 O(n)两个辅助数组。关键操作f[i] f[i-1] nums[i-1]前缀递推、g[j] g[j1] nums[j1]后缀递推、if (f[i] g[i]) return i;中心判定。 例子单元素数组的边界nums [5]f[0] 0、g[0] 0比较f[0] g[0]成立返回0——该元素左右两侧均为空和为 0天然是中心若漏掉 f[0]/g[0] 的初始化这里会比较到未定义值结果不确定。五、返回值目标映射返回第一个满足f[i] g[i]的i中心下标全部不满足返回-1对应题目不存在则返回 -1。三.代码class Solution { public: int pivotIndex(vectorint nums) { int n nums.size(); // 1. 初始化两个辅助数组f 记录左侧和g 记录右侧和 vectorint f(n); // f[i] 下标 i 左侧所有元素之和 vectorint g(n); // g[i] 下标 i 右侧所有元素之和 f[0] 0; // 下标 0 左侧没有元素和为 0 g[n - 1] 0; // 下标 n-1 右侧没有元素和为 0 // 2. 构建前缀数组 f从左往右累加不含 nums[i] 自身 for (int i 1; i n; i) { f[i] f[i - 1] nums[i - 1]; } // 3. 构建后缀数组 g从右往左累加不含 nums[j] 自身 for (int j n - 2; j 0; j--) { g[j] g[j 1] nums[j 1]; } // 4. 从左到右找第一个左右和相等的位置 for (int i 0; i n; i) { if (f[i] g[i]) { return i; // 左侧和 右侧和即中心下标 } } // 5. 不存在中心下标 return -1; } };四、易错点分析难点1f[i]、g[i] 的语义——不含 nums[i] 本身f[i] f[i - 1] nums[i - 1]; // 加的是 nums[i-1]不是 nums[i] g[j] g[j 1] nums[j 1]; // 加的是 nums[j1]不是 nums[j]f[i] 表示 i左侧的和所以递推时加的是nums[i-1]g[i] 表示 i右侧的和加的是nums[j1]。最容易写错的是下标偏移若写成f[i] f[i-1] nums[i]f[i] 会把自身算进去所有位置的左右和整体错位比较结果完全失真。难点2两个数组的构建方向相反for (int i 1; i n; i) // f从左往右 for (int j n - 2; j 0; j--) // g从右往左f 依赖前一个f[i-1]必须正向遍历g 依赖后一个g[j1]必须反向遍历。方向写反时f 会访问未初始化的 f[i-1]越界或取到垃圾值g 同理——这是两个循环最隐蔽的错误且编译器不会报错。难点3f[0] 0、g[n-1] 0 的边界初始化f[0] 0; // 最左端左侧无元素 g[n - 1] 0; // 最右端右侧无元素vectorint默认初始化为 0不写这两行也能跑但语义必须明确中心下标可能是 0整个数组左侧为空或 n-1右侧为空。若漏掉初始化并误用其他构造方式如vectorint f(n, -1)首尾位置会永远无法命中中心。难点4为什么返回第一个满足的 i 就是最左侧for (int i 0; i n; i) { if (f[i] g[i]) return i; // 立即返回 }题目要求若有多个中心下标返回最左侧的那个。从左到右扫描并首次命中即返回天然满足最左侧要求。若改成记录最后一个或收集全部会违反题意或改变返回值。五、流程图 闭幕 恭喜你完成了「寻找数组的中心下标」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题使用前缀和数组f和后缀和数组g分别记录每个位置左侧和右侧的元素和。为什么f[0] 0和g[n-1] 0是合理的如果中心下标在端点0 或 n-1这种初始化如何处理构建f数组时f[i] f[i-1] nums[i-1]为什么不包含nums[i]自身如果包含自身判定条件需要如何调整本题采用了两个辅助数组空间复杂度为 O(n)。能否只用一个变量前缀和配合数组总和来完成判断如果可以请描述思路。如果数组元素包含负数当前算法是否仍然正确中心下标的定义是否受影响延伸挑战如果要求不借助额外数组仅使用 O(1) 空间解决本题请写出核心思路。如果你觉得本文对你有所帮助欢迎点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案f[0]0和g[n-1]0是合理的因为端点左侧或右侧没有元素总和为 0。若中心下标在端点只需另一端和也为 0 即可满足条件例如nums[1]中心下标为 0。不包含自身是因为中心下标的定义要求“左右两侧元素和相等”不包括自身若包含自身则条件变为f[i] nums[i] g[i]仍需调整。可优化为 O(1) 空间先计算数组总和total然后从左向右扫描维护leftSum左侧和右侧和 total - leftSum - nums[i]比较leftSum rightSum即可无需两个数组。负数不影响因为判断的是“和相等”负数只影响数值大小不改变相等逻辑算法完全适用。延伸挑战答案挑战2O(1) 空间思路见上方答案先求总和total再左扫描维护leftSum用total - leftSum - nums[i]得到右侧和比较相等即可。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨