算法28，前缀和，寻找数组中的中心下标

这份笔记的核心内容是解决算法题“寻找数组的中心下标”LeetCode 724。简单来说就是找到一个下标i使得该位置左边所有数字的和等于右边所有数字的和。如果存在多个返回最左边的那个。笔记中记录了两种解法其中解法二利用前缀和/前后缀和是最优解。1. 核心思路解析方法一暴力法笔记上方不推荐思路对于每个位置i都重新遍历一遍数组分别计算左边和右边的和然后进行比较。缺点时间复杂度高为 O(N2)。笔记中也写了“暴力每次枚举中心下标左边一遍右边一遍”。方法二前缀和 后缀和笔记下方推荐这是笔记重点推导的方法利用了空间换时间的思想。定义两个数组f数组前缀和f[i]表示从数组开头0到i位置的所有元素之和从左往右累加。公式f[i] f[i-1] nums[i-1]g数组后缀和g[i]表示从数组末尾n-1到i位置的所有元素之和从右往左累加。公式g[i] g[i1] nums[i1]判断逻辑遍历数组如果某个位置i满足f[i] g[i]说明左边和等于右边和i就是中心下标。为了节省空间实际上可以只算一次总和total然后在遍历时动态计算右边和right total - left - nums[i]但笔记中使用的是更直观的数组记录法。2. 代码实现Java 版根据笔记中的代码逻辑整理如下public int pivotIndex(int[] nums) { int n nums.length; // 1. 定义并初始化 f 和 g 数组 // f[i] 存储 [0, i-1] 的元素和 int[] f new int[n]; // g[i] 存储 [i1, n-1] 的元素和 int[] g new int[n]; // 2. 计算前缀和 f (从左往右推) // 注意笔记中写的是 f[i] f[i-1] nums[i-1] for (int i 1; i n; i) { f[i] f[i - 1] nums[i - 1]; } // 3. 计算后缀和 g (从右往左推) // 注意笔记中写的是 g[i] g[i1] nums[i1] for (int i n - 2; i 0; i--) { g[i] g[i 1] nums[i 1]; } // 4. 遍历寻找中心下标 for (int i 0; i n; i) { // 如果左边和(f[i])等于右边和(g[i])返回下标 i if (f[i] g[i]) { return i; } } // 5. 没找到返回 -1 return -1; }3. 关键点解析对应笔记细节初始化边界f[0] 0因为第 0 个元素的左边没有任何元素和为 0。g[n-1] 0因为最后一个元素的右边没有任何元素和为 0。递推公式f[i] f[i-1] nums[i-1]当前的前缀和 前一个位置的前缀和 前一个位置的值。g[i] g[i1] nums[i1]当前的后缀和 后一个位置的后缀和 后一个位置的值。4. 进阶优化空间复杂度 O(1)如果觉得开两个数组太占内存可以只用一个变量记录左边和右边和用“总和 - 左边和 - 当前值”算出来public int pivotIndexOptimize(int[] nums) { int total 0; for (int num : nums) total num; // 先算总和 int leftSum 0; for (int i 0; i nums.length; i) { // 右边和 总和 - 左边和 - 当前元素 if (leftSum total - leftSum - nums[i]) { return i; } leftSum nums[i]; // 更新左边和 } return -1; }