【优选算法必刷100题】第027~28题（前缀和算法）：寻找数组的中心下标、除自身以外数组的乘积
🔥艾莉丝努力练剑：个人主页
❄专栏传送门：《C语言》、《数据结构与算法》、C/C++干货分享&学习过程记录、Linux操作系统编程详解、笔试/面试常见算法：从基础到进阶
⭐️为天地立心，为生民立命，为往圣继绝学，为万世开太平
🎬艾莉丝的简介：
🎬艾莉丝的算法专栏简介：
目录
027 寻找数组的中心下标
力扣链接：724. 寻找数组的中心下标
力扣题解链接：前缀和优化法解决【寻找数组的中心下标】问题
题目描述：
1.1 算法思路：前缀和
我们根据中心下标的定义可知：除中心下标的元素外，该元素左边的前缀和】等于该元素右边的【后缀和】——
（1）因此，我们可以先预处理出来两个数组，一个表示前缀和，另一个表示后缀和。
（2）然后，我们可以用一个for循环枚举可能的中心下标，判断每一个位置的「前缀和」以及【后缀和】，如果二者相等，就返回当前下标。
1.2 算法实现
1.2.1 C++实现
代码演示如下——
class Solution { public: int pivotIndex(vector<int>& nums) { // 数组大小 int n = nums.size(); vector<int> f(n),g(n); // // 细节处理 // int f[0] = 0,g[n - 1] = 0; // 1、预处理前缀和数组和后缀和数组 for(int i = 1;i < n;i++) // f[0] = 0，如果i = 0开始会发生越界访问 f[i] = f[i - 1] + nums[i - 1]; for(int i = n - 2;i >= 0;i--) g[i] = g[i + 1] + nums[i + 1]; // 2、使用 for(int i = 0;i < n;i++) if(f[i] == g[i]) return i; return -1; } };时间复杂度：O(n)，空间复杂度：O(1)。
1.2.2 Java实现
代码演示如下——
class Solution { public int pivotIndex(int[] nums) { // lsum[i] 表示：[0, i - 1] 区间所有元素的和 // rsum[i] 表示：[i + 1, n - 1] 区间所有元素的和 int n = nums.length; int[] lsum = new int[n]; int[] rsum = new int[n]; // 预处理前缀和后缀和数组 for (int i = 1; i < n; i++) lsum[i] = lsum[i - 1] + nums[i - 1]; for (int i = n - 2; i >= 0; i--) rsum[i] = rsum[i + 1] + nums[i + 1]; // 判断 for (int i = 0; i < n; i++) if (lsum[i] == rsum[i]) return i; return -1; } }时间复杂度：O(n)，空间复杂度：O(1)。
1.3 博主手记
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己能够推导很重要！
028 除自身以外数组的乘积
力扣链接：238. 除自身以外数组的乘积
力扣题解链接：前缀后缀乘积法解决【除自身以外数组的乘积】
题目描述：
2.1 算法思路
注意题目的要求，不能使用除法，并且要在O（N)的时间复杂度内完成该题。那么我们就不能使
用暴力的解法，以及求出整个数组的乘积，然后除以单个元素的方法。
继续分析，根据题意，对于每一个位置的最终结果ret[i]，它是由两部分组成的：
（1）nums[0] * nums[1] * nums[2] * ... *nums[i - 1]
（2）nums[i + 1] * nums[i + 2] * ... * nums[n - 1]
于是，我们可以利用前缀和的思想，使用两个数组post和suf，分别处理出来两个信息：
（1）post表示：i位置之前的所有元素，即[0，i - 1]区间内所有元素的前缀乘积；
（2）suf表示：i位置之后的所有元素，即[i + 1，n - 1]区间内所有元素的后缀乘积然后再处理最终结果。
2.2 算法实现
2.2.1 C++实现
代码演示如下——
class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { // lprod 表示：[0, i - 1] 区间内所有元素的乘积 // rprod 表示：[i + 1, n - 1] 区间内所有元素的乘积 int n = nums.size(); vector<int> lprod(n + 1), rprod(n + 1); lprod[0] = 1, rprod[n - 1] = 1; // 预处理前缀积以及后缀积 for (int i = 1; i < n; i++) lprod[i] = lprod[i - 1] * nums[i - 1]; for (int i = n - 2; i >= 0; i--) rprod[i] = rprod[i + 1] * nums[i + 1]; // 处理结果数组 vector<int> ret(n); for (int i = 0; i < n; i++) ret[i] = lprod[i] * rprod[i]; return ret; } };时间复杂度：O(n)，空间复杂度：O(1)。
2.2.2 Java实现
代码演示如下——
class Solution { public int[] productExceptSelf(int[] nums) { // lprod 表示：[0, i - 1] 区间内所有元素的乘积 // rprod 表示：[i + 1, n - 1] 区间内所有元素的乘积 int n = nums.length; int[] lprod = new int[n]; int[] rprod = new int[n]; lprod[0] = 1; rprod[n - 1] = 1; // 预处理前缀积以及后缀积 for (int i = 1; i < n; i++) lprod[i] = lprod[i - 1] * nums[i - 1]; for (int i = n - 2; i >= 0; i--) rprod[i] = rprod[i + 1] * nums[i + 1]; // 处理结果数组 int[] ret = new int[n]; for (int i = 0; i < n; i++) ret[i] = lprod[i] * rprod[i]; return ret; } }时间复杂度：O(n)，空间复杂度：O(1)。
2.3 博主手记
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己能够推导很重要！
结尾
往期回顾：
【优选算法必刷100题】第025~26题（前缀和算法）：【模版】前缀和、【模板】二维前缀和
结语：都看到这里啦！请大佬不要忘记给博主来个“一键四连”哦！
🗡博主在这里放了一只小狗，大家看完了摸摸小狗放松一下吧！🗡
૮₍ ˶ ˊ ᴥ ˋ˶₎ა
