前缀和（下）

目录

热身：

寻找数组的中心下标

题解：

代码：

进阶：

除自身之外数组的乘积

题解：

代码： 

和为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;}
};