前缀和（更新中）

目录

1.寻找数组的中心下标

2.除自身以外数组的乘积

3.和为k的子数组

4.可被k整除的子数组

5.连续数组

---

1.寻找数组的中心下标

. - 力扣（LeetCode）

class Solution {
public:int pivotIndex(vector<int>& nums) {int size = nums.size();vector<int>f(size);vector<int>g(size);f[0] = nums[0];for(int i = 1; i < size; i++){f[i] = f[i-1]+nums[i];}g[size-1] = nums[size-1];for(int i = size-2; i >= 0; i--){g[i] = g[i+1] + nums[i];}for(int i = 0; i < size; i++){if(f[i] == g[i])return i;}return -1;}
};

        即中心下标左边与右边的元素和相等，如果没有某一侧没有元素，那么值为0.

        因为是加法运算，那么左右元素相等的情况，加上中心元素，左右元素依然相等。

        f[i]为前缀和，表示从0到i位置的数组元素和，递推公式为  f[i] = f[i-1]+nums[i];

        g[i]为后缀和，表示从 size-1 到i位置的数组元素和，递推公式为·g[i] = g[i+1] + nums[i];

        初始化时，f【0】，g【size-1】为0，不干扰运算

2.除自身以外数组的乘积

. - 力扣（LeetCode）

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int size = nums.size();vector<int>f(size);vector<int>g(size);vector<int>ret(size);f[0] = 1;g[size-1] = 1;for(int i = 1; i < size; i++){f[i] = f[i-1]*nums[i-1];}for(int i = size-2; i >= 0; i--){g[i] = g[i+1]*nums[i+1];}for(int i = 0; i < size; i++){ret[i] = f[i]*g[i];}return ret;}
};

          即某下标左边与右边的元素的积，如果没有某一侧没有元素，那么值为1.

        f[i]为前缀积，表示从0到i-1位置的数组元素积，递推公式为  f[i] = f[i-1]*nums[i-1];

        g[i]为后缀积，表示从 size-1 到i+1位置的数组元素和，递推公式为·g[i] = g[i+1] * nums[i+1];

        初始化时，f【0】，g【size-1】为1，不干扰运算

3.和为k的子数组

. - 力扣（LeetCode）

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int>hash;int sum = 0;int ret = 0;hash[0] = 1;for(auto ch: nums){sum += ch; ret+= hash[sum-k];hash[sum]++;}return ret;}
};

        因为数组中的元素有正有负，并不具有单调性，因此不能使用滑动窗口，那么我们使用前缀和。

        以下标为i的位置为终点，dp【i】为从nums【0】加到nums【i】的和

         1 6 -3 2 9 .....x

        0 1  2  3  4.... i

        要想找到其中一段子数组和为k，可以等效为找从0向后找一个子数组，和为dp【i】-k。

        因为每次只找i之前的位置，因此我们不需要真的创建一个前缀和，只需要记录一个变量sum，来记录此时的前缀和。

        创建一个哈希表<int，int>分别存储某个前缀和的值，和它的数目。

        前缀和sum从0开始，加入哈希表，因此会缺失数组中无元素的情况，所以我们应该初始化hash【0】 = 1.

        我们每遍历到一个前缀和sum的时候，只需要加上已经在hash中存储的，即i位置之前的前缀和中，是否有值为sum-k，加上即可，然后再加上本次增添的前缀和

4.可被k整除的子数组

. - 力扣（LeetCode）

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int,int>hash;int sum = 0;int ret = 0;hash[0] = 1;for(auto ch: nums){sum += ch; ret+= hash[((sum%k)+k)%k];hash[((sum%k)+k)%k]++;}return ret;}
};

思路同3完全相同

注意点：1.c++和java中负数取余操作为负数,因此我们需要把取余操作的值+取余的值，再取余。

2.我们哈希表中存的是前缀和取余后的值。原因如下

0 1 2 3 4 ....i

假设从下标4到i的数组和能被k整除，即，（前缀和i-前缀和3）% k == 0

根据同余定理，前缀和i % k == 前缀和3 % k。

5.连续数组

. - 力扣（LeetCode）

class Solution {
public:int findMaxLength(vector<int>& nums) {for(auto& ch : nums){if(ch == 0)ch = -1;}int size = nums.size();unordered_map<int,int>hash;int sum = 0;hash[0] = 1;int ret = 0;for(int i = 0; i < size; i++){sum += nums[i];if(hash[sum])ret = max(ret,i+2-hash[sum]);else hash[sum] = i+2;}return ret;}
};

        直接做不好做，我们先把0转化为-1，这样子当0与1数目相等时，其和为0。

        这样我们就把题目转化为类似第三题的和为k的数组，此时和为0.

        因此我们只需要寻找两个前缀和相等的数组，将他们的下标相减即可。

        所以我们哈希表中储存该下标，hash[0]中储存-1.

        接着我们遍历数组每次求出前缀和的时候，到哈希表中查看，如果已经储存下标，那么我们相减。并与前面已经求出的下标差求最大，否则我们把下标填入。下标只需要更新最前面一个，因为向后更新时距离永远是更小的。

        但是在判断条件的时候我们遇到了问题，若更新出的数组下标为0，那么我们将无法判断，因此我们统一将数组下标+2，这样结果不变。