前缀和（下）
目录
热身：
寻找数组的中心下标
题解：
代码：
进阶：
除自身之外数组的乘积
题解：
代码：
和为K的子数组
题解：
代码：
和可被 K 整除的子数组
题解：
同余定理：
为什么需要修正负数取模？
代码：
连续数组
代码：
热身：
寻找数组的中心下标
724. 寻找数组的中心下标 - 力扣（LeetCode）
https://leetcode.cn/problems/find-pivot-index/description/
题解：
运用前缀和就可以解决这个问题，注意在本题中，中心下标的左侧数之和、右侧数之和均不包括中心下标的数。
我们定义前缀和、后缀和数组，根据题目要求，对前缀和数组的最左端、后缀和数组的最右端初始化为0。
代码：
class Solution {
public:int pivotIndex(vector<int>& nums) {int n=nums.size();vector<int> f(n);//前缀和vector<int> g(n);//后缀和f[0]=g[n-1]=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. 除自身以外数组的乘积 - 力扣（LeetCode）https://leetcode.cn/problems/product-of-array-except-self/description/
题解：
由于题目要求不用除法，所以我们不可以算出数组全部元素的乘积后再去除以 nums[ i ] 来得到答案。
在寻找数组的中心下标中，我们算出了 nums[ i ] 左侧和、右侧和，我们可以按照这个思路，算出 nums[ i ] 左侧乘积、右侧乘积，把左右两侧乘积相乘，就可以得到除自身之外数组的乘积。
代码：
class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n=nums.size();vector<int> f(n);//左侧乘积vector<int> g(n);//右侧乘积vector<int> ret(n);//返回值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];for(int i=0;i<n;i++){ret[i]=f[i]*g[i];}return ret;}
};和为K的子数组
560. 和为 K 的子数组 - 力扣（LeetCode）https://leetcode.cn/problems/subarray-sum-equals-k/description/
题解：
如下图，假设 k = 10，在给定的数组中，发现下标 2 ~ 5 的数组和 = k，而这一部分数组和，恰好为下标 0 ~ 5 的前缀和 - 下标 0 ~ 1 的前缀和（假设前缀和数组为 sum，则 K = sum[ 5 ] - sum[ 1 ] ），所以我们可以用前缀和数组，快速得到和为 K 的子数组。
为了获得和为 K 的子数组的个数，我们可以在计算前缀和的同时，用哈希表记录每一个前缀和出现的次数。
比如 K = sum[ 5 ] - sum[ 1 ] ，可以交换位置，变为 sum[ 5 ] - K = sum[ 1 ]，由于记录了 sum[ 1 ] 出现的次数为 1 次，这样就可以得出当前和为 K 的子数组的个数为 1 个。
由于我们用哈希表记录了每一个前缀和出现的个数，所以前缀和的计算可以不采用数组。
可能会出现以下情况：前缀和 sum - k == 0，但是哈希表中记录的前缀和并不存在 0，怎么处理？
既然哈希表中不存在前缀和 0，那我们可以先放一个 0 进去，并把出现的次数设置为 1.
代码：
class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int> hash;int ret=0,sum=0;hash[0]=1;for(int i=0;i<nums.size();i++){sum+=nums[i];if(hash.count(sum-k)) {ret+=hash[sum-k];}hash[sum]++;}return ret;}
};和可被 K 整除的子数组
974. 和可被 K 整除的子数组 - 力扣（LeetCode）https://leetcode.cn/problems/subarray-sums-divisible-by-k/description/
题解：
同余定理：
假设 a % k == b % k ，则 （ a - b ) % k = 0.
举个例子，假设 k = 5，23 % 5 = 13 % 5，则（23 - 23 ）% 5 = 0.
我们可以运用同余定理来解决这道题：
和上一题的思路相似，我们用 i 遍历数组，计算出下标 0 ~ i 的前缀和 sum，用哈希表记录 sum % K 出现的次数，如果 sum % K 曾经出现过，则存在和可被 K 整除的子数组，返回值 += 次数。
以示例 1 为例，假设返回值为 ret，比如下标 0 ~ 1 的前缀和取模后为 4，而下标 0 的前缀和取模后也为 4 ，而在此之前取模后为 4 出现的次数为 1，根据同余定理，子数组 [ 5 ] 可以被 K 整除，ret += 1，同理，下标 0 ~ 2 的前缀和取模后为 4，而在此之前取模后为 4 出现的次数为 2 ，所以此时 ret+=2 ，分别为 [ 5 ] , [ 5 , 0 ] , [ 0 ] ；下标 0 ~ 4 的前缀和取模后为 4，而在此之前取模后为 4 出现的次数为 3，所以此时 ret += 3 ，和可被 K 整除的子数组有 6 个，分别为 [ 5 ] , [ 5 , 0 ] , [ 0 ], [ 0, -2 , -3 ] , [ -2 , -3 ] ，[ 5 , 0, -2 , -3 ] ，以此类推。
注意 0 也可以被 K 整除！
为什么需要修正负数取模？
我们观察下面的例子：
存在子数组 [ 2, 3, 4 ] 的和可以被 3 整除，但是这在前缀和中无法体现出来。
再举个例子：
1、 7 % 3 = 1 , ( -2 ) % 3 = -2 ，但 [ 7 - ( -2 ) ] % 3 = 0 ；
2、（ - 2） % 3 = -2 , ( -5 ) % 3 = -2 ，[ -2 - ( -5 ) ] % 3 = 0 。
可以看出当 a、b 同正同负时， a % k == b % k ，可以推出 （ a - b ) % k = 0，可以推出和可被 K 整除的子数组，但 a、b一正一负时，就没办法推出。
为了让同余定理在一正一负的情况下也可以成立，我们可以对负数取模进行修正，把取模后的结果修改为正数，这样 a、b 就都是正数：
int r=(sum%k+k)%k;再回到一开始举的例子，通过修正取模后，就可以得到正确的结果：
代码：
class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {int sum=0,ret=0;unordered_map<int,int> hash;hash[0]=1;for(int i=0;i<nums.size();i++){sum+=nums[i];int r=(sum%k+k)%k;if(hash.count(r)) ret+=hash[r];hash[r]++;}return ret;}
};连续数组
525. 连续数组 - 力扣（LeetCode）
这道题用到的方法比较巧妙，利用了前缀和，
1、如果 nums[ i ] 为 0，则 sum += -1；
2、如果 nums[ i ] 为 1，则 sum += 1。
如果此时的前缀和 sum 在之前已经出现过了，假设上一次出现的下标为 j，说明 i 和 j 中间的这段数组的 0 和 1 的数量相等，只有相等了，才会相互抵消，前缀和才会再次变为 sum。
代码：
class Solution {
public:int findMaxLength(vector<int>& nums) {unordered_map<int,int> hash;hash[0]=-1;int ret=0;int sum=0;for(int i=0;i<nums.size();i++){sum+=(nums[i]==0?-1:1);if(hash.count(sum)) ret=max(ret,i-hash[sum]);else hash[sum]=i;}return ret;}
};