专题五_前缀和_算法专题详细总结

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n=nums.size();
        vector<int> ret1(n+1);
        vector<int> ret2(n+2);

        for(int i=1;i<=n;i++) ret1[i]=ret1[i-1]+nums[i-1];
        for(int i=n;i>0;i--) ret2[i]=ret2[i+1]+nums[i-1];

        for(int i=1;i<=n;i++)
            if(ret1[i]==ret2[i]) return i-1;
        return -1;
    }
};

总结：

像这种求前缀和跟后缀和的题目形式比较固定，都比较好想。

2. 除⾃⾝以外数组的乘积（medium）

解析：

1.暴力：

任然会超时，时间复杂度达到O(N^2) ，想想都可怕

2.前缀和

优化是利用前缀和 跟 后缀和 来分别求出乘积，前缀和用f[i] 表示 ，后缀和用g[i] 表示。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> f(n+1,1),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> dp(n);
        for(int i=0;i<n;i++)
        {
            dp[i]=f[i]*g[i];
        }
        return dp;
    }
};

总结：

1.前缀积 和 后缀积 跟上一题一样，这题不能取i 位置的nums[i] 的值，而是取nums[i] 前面所有数的乘积和nums[i] 后面所有数的乘积；为了不在相乘过程中数都变成0，所以将f,g都初始化为1.
2.那么同样是设置两个函数f[i] 和 g[i] 对于f[i] 存取的是【0，i-1】区间的积，对于g[i] 存取的是【i+1，n-1】 区间的积，那么为了防止越界，f从1，开始，f从n-2开始
最后就是存到数组ret里面，都是取从i==0开始到i==n-1结束，因为考虑到dp[0]这个时候，f[0]==1 * g[0] ,那么这个g[0] 就应该是除了nums[0] 外，所有元素的乘积，所以，dp[i]=f[i]*g[i] 都是从0开始到n-1结束

3. 和为 k 的⼦数组（medium）

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        hash[0]=1;
        int ret=0,sum=0;
        for(auto e : nums)
        {
            sum+=e;
            //sum-k 在前面数组就存在过的话，这里的sum一直在改变，所以sum-k也一直在改变
            //每次就是在前缀和里面找sum-k
            if(hash.count(sum-k)) ret+=hash[sum-k];
            hash[sum]++;
        }        
        return ret;
    }
};

总结：

这题有点难，我们只需要每次统计在[0,i-1]区间内，有多少个前缀和等于sum[i]-k即可，因为找数组和==k，就相当于，在前缀和里找sum[i]-k,那每次都将前缀和存入hash，然后在hash里找sum[i]-k,就可以得到次数如果能够满足条件，就相当于，一个大的前缀和数组里，有一个满足条件的小前缀和数组。我要在【0，i】区间找一段区间【j,i】和为k，那么区间【0，j-1】这个区间和就是sum[i]-k,那么这个就是较小的那个前缀和。当我在hash里找到这个小前缀和等于这个sum[i]-k,那么就满足这个条件。当整个数组和为k，这也是一种情况，那么hash[0]==1,就是为了当满足这种情况的时候，ret能+=1

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        //对负数取模 （a%p+p）%p
        unordered_map<int,int> hash;
        hash[0]=1;//默认0%k依旧等于0
        int sum=0,ret=0;
        for(auto e : nums)
        {
            sum+=e;
            if(hash.count((sum%k+k)%k)) ret+=hash[(sum%k+k)%k];
            hash[(sum%k+k)%k]++;
        }
        return ret;
    }
};

5. 连续数组（medium）

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

总结：

将数组内0 全部变成-1 后就是求子数组最大长度和为0的长度，那么前面有一题是求和为k 的子数组出现的次数，那么这题就有点细节上的不一样，对于hash表内存的还是前缀和，那么就是sum，但是后面存的就是sum的下标，来计算两个下标之间的最大值。

6. 矩阵区域和（medium）

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int n=mat.size(),m=mat[0].size();
        //构建前缀和矩阵
        vector<vector<int>> dp(n+1,vector<int>(m+1));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+mat[i-1][j-1];
        
        //使用前缀和数组
        vector<vector<int>> ret(n,vector<int>(m));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                int x2=min(n,i+k+1),y2=min(m,j+k+1);
                int x1=max(1,i-k+1),y1=max(1,j-k+1);
                ret[i][j]=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];
            }
        }
        return ret;
    }
};

总结：

对于使用构建好的前缀和矩阵，把他重新装入ret矩阵里面，就要控制好边界条件。(x1,y1)取max (x2,y2)取min，减去包含重复的元素即可。

总结一下吧~，前缀和对我来说难度有点大，但是只要这些题目多做几遍，其实也就是那些模板题，希望对你也有帮助！！！