我爱学算法之—— 前缀和（中）
一、724. 寻找数组的中心下标
题目解析
这道题，给定数组nums，要求我们找出这个数组的中心下标。
**中心下标：**指左侧所有元素的和等于右侧所有元素的和。
如果存在多个中心数组下标，就返回最左侧的中心数组下标。
算法思路
暴力解法：
对于这道题，要找出数组的中心下标，暴力解法就是遍历数组，依次判断该位置中心下标（左侧所有元素等于右侧所有元素）。
对于暴力解法，遍历数组nums；
遍历到i位置时，判断该位置是否是中心下标，也就是该位置左侧所有元素是否等于右侧所有元素。
优化：
暴力解法要遍历数组，遍历到i位置时还需求左侧所有元素的和、右侧所有元素的和，就还需再遍历数组来求。
时间复杂度就是O(n)；对于遍历数组的每一个元素，依次判断该位置是否是中心下标，这里进行不了优化；
那就来看：遍历到i位置时，求左侧所有元素的和、右侧所有元素的和
在暴力解法中，我们就遍历i位置左侧的所有元素，求左侧所有元素的和；遍历i位置右侧所有元素的和，求右侧所有元素的和。
我们可不可以使用更简单的方法来拿到i位置所有元素的和？
当然是可以的，我们可以预先处理前缀和与后缀和数组，这样就可以以O(1)的时间复杂度拿到i位置左侧所有元素的和、i位置右侧所有元素的和。
前缀和：预处理前缀和、后缀和数组：遍历到i位置时需要i位置前面所有元素的和，i位置后面所有元素的和；这里预先处理前缀和数组f和后缀和数组g前缀和数组f：f[i]表示区间[0,i-1]中所有元素的和。（i位置前面所有元素的和）后缀和数组g：g[i]表示区间[i+1 , n-1]中所有元素的和。（i位置后面所有元素的和）**使用前缀和、后缀和数组：**有了前缀和、后缀和数组，在遍历到i位置时只需判断f[i]是否等于g[i]即可。如果f[i] == g[i]，就表示i位置是一个中心位置，返回该位置下标i即可。如果f[i] != g[i]，就表示i位置不是应该中心位置，继续向后遍历即可。
预处理前缀和：
这里f[i]表示的是[0 , i-1]中所有元素的和，所以在填表时从1开始向后填表；f[i] = f[i-1] + nums[i];表示的是
g[i][i+1 , n-1]中所有元素的和，所以在填表时从n-2开始向前填表；g[i] = g[i+1] + nums[i];
初始化：在填f[1]时会用到f[0]，而f[0]表示的是[0,-1]中所有元素的和，该区间不存在。所以初始化f[0] = 0在填g[n-2]时会用到g[n-1]，而g[n-1]表示[n,n-1]中所有元素的和，该区间不存在、所以初始化g[n-1] = 0
代码实现
classSolution{public:int f[10002];//[0 , i-1]int g[10002];//[i+1 , n-1]intpivotIndex(vector<int>& nums){int n = nums.size(); f[0]=0; g[n]=0;for(int i =1; i <= n; i++) f[i]= f[i -1]+ nums[i -1];for(int i = n -2; i >=0; i--) g[i]= g[i +1]+ nums[i +1];for(int i =0; i < n; i++){if(f[i]== g[i])return i;}return-1;}};二、238. 除自身以外数组的乘积
题目解析
对于这道题，给定一个数组nums，要求出数组answer；
其中anwser[i]表示nums数组中除了nums[i]以外的所有数的乘积。
算法思路
对于这道题，要返回数组answer，其中answer[i]表示除了nums[i]以外的所有数的乘积。
那也就是说，我们需要求出nums中每一个元素对应的answer[i]。
暴力解法：
遍历整个数组nums，遍历到i位置时，再遍历整个数组计算除了i位置之外其他所有数的乘积。
这里时间复杂度就是O(n^2)。
优化
这里当我们遍历到i位置时，暴力解法就是再次遍历数组，来计算除了i以外的所有数的乘积。
也就是以O(n)的时间复杂度来获取除了i位置意外所有数的乘积。
这里我们可不可以通过预先处理，来直接就可以拿到除了i位置意外的所有数的乘积。
这里，当遍历到i位置时，我们可以发现i位置把整个数组分成了两部分：
一部分是区间[0 , i-1]、另一部分则是区间[i+1 , n-1]；
那我们只要拿到区间[0 , i-1]中所有数的乘积，区间[i+1 , n-1]中所有数的乘积那就可以直接计算除了i位置以外所有数的乘积。
前缀和(积)
所以，我们就可以通过预先处理前缀积数组，在遍历到i位置时，就可以以O(1)的时间复杂度获取到除了i位置以外的所有数的积。
前缀积数组：f[i]表示区间[0 , i-1]中所有数的积后缀积数组：g[i]表示区间[i+1 , n-1]中所有数的积
预处理前/后缀积数组：前缀积：f[i] = f[i-1] * nums[i-1]后缀积：g[i] = g[i+1] * nums[i+1]
使用前/后缀积数组：
在遍历到i位置时，除i位置以外的所有数的乘积sum = f[i] * g[i]。（这里就可以使用O(1)的时间复杂度获取除i位置以外的所有数的乘积）
初始化：在预处理前缀积数组时，f[1]会用到f[0]，而区间[0,-1]显然不存在；为了不影响前缀积数组中的其他数，将f[0]初始化为1。在预处理后缀积数组时，g[n-2]会用到g[n-1]，而区间[n , n-1]显然不存在；为了不影响后缀积中的其他数，将g[n-1]初始化为1。
细节：前缀积：前缀积数组f[i]表示区间[0 , i-1]中所有数的积，在预处理时要处理到n位置。（从前往后）后缀积：后缀积数组g[i]表示区间[i+1 , n-1]中所有数的积，在预处理时就要处理到0位置。（从后往前）
代码实现
classSolution{public:int f[100001];int g[100001]; vector<int>productExceptSelf(vector<int>& nums){int n = nums.size(); f[0]= g[n -1]=1;for(int i =1; i <= n; i++){ f[i]= f[i -1]* nums[i -1];}for(int i = n -2; i >=0; i--){ g[i]= g[i +1]* nums[i +1];} vector<int>ret(n);for(int i =0; i < n; i++){ ret[i]= f[i]* g[i];}return ret;}};三、560. 和为 K 的子数组
题目解析
对于这道题，给定一个数组nums和一个整数k
我们要求在nums数组中存在多少个和为k的子数组。
注意：这道题中给的的数据范围：-1000 <= nums[i] <= 1000
算法思路
暴力解法：
首先，对于这道题，暴力解法就是枚举：枚举所有的子数组，然后找出和为k的子数组的个数。
枚举所有子数组，以i为起始位置，j为结束位置的子数组；
求出子数组的和，然后找到子数组和为k的个数。
前缀和：
在暴力解法枚举所有子数组中，本质就是先固定i位置，再枚举以i位置为起始位置的子数组，寻找和为k 的子数组。
那我们也可以先固定i位置，再枚举所有以i位置为结束位置的子数组，然后在这些子数组中，找到和为k的子数组。
所以，我们在遍历数组时，就可以先固定i位置，再枚举以i位置为结束位置的所有子数组，在这些子数组中找和为k的子数组
那如何去找呢？
在遍历到i位置时，我们要找以i位置为结束位置的所有子数组这和为k的子数组的个数；
那我们就可以将问题转换以下：在区间[0 , i]中寻找前缀和为sum - k的个数。
所以，我们就可以在区间[0 , i-1]中找前缀和为sum - k的个数，找到的就是以i为结束位置、和为k的子数组的个数。
所以，现在我们预处理处一个前缀和数组，然后遍历nums数组，遍历到i位置时就要在区间[0 , i-1]中找前缀和等于sum - k的数量
但是这样来解的话，时间复杂度貌似还不如暴力解法啊，时间复杂度为O(n^2 + n)啊。
hash表优化：
我们知道了使用前缀和如何去求以i位置为结束位置、和为k的子数组的个数；但是时间复杂度却不如暴力解法。
原因就是：在遍历i位置时我们还需要去遍历区间[0 , i-1]中的所有前缀和，才能够知道前缀和为sum - k的数量。
这里要求前缀和为sum - k的数量，就可以使用hash表来优化：
在遍历到i位置时，hash表中存储区间[0 , i-1]中所有前缀和以及前缀和出现的次数。（这样我们就可以直接获取前缀和为sum - k的数量。
细节问题：hash表中存储的是区间[0 , i-1]中所有的前缀和以及前缀和出现的次数；所以在遍历数组的过程中，依次统计前缀和出现的次数。初始情况下hash中一个存在前缀和为0，出现次数为1的元素：(0 , 1)；如果整个数组的和为k，只有存在(0 , 1)才能统计上这种情况。使用一个数sum来代替整个前缀和数组；这里没有必要去预处理一个前缀和数组，只需用sum即可代替；sum表示遍历到i位置时，区间[0 , i]位置的和；这样i位置之前的前缀和都被统计在hash表中，而i位置后面的前缀和不需要。
代码实现
classSolution{public:intsubarraySum(vector<int>& nums,int k){int n = nums.size(); unordered_map<int,int> hash; hash[0]=1;int sum =0, ret =0;for(int i =0; i < n; i++){ sum += nums[i];if(hash.count(sum - k)) ret += hash[sum - k]; hash[sum]++;}return ret;}};到这里本篇文章内容就结束了，感谢各位的支持
继续加油！！！
