自学内容网 自学内容网

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

目录

前缀和

1. 【模板】⼀维前缀和(easy)

总结:

2. 【模板】⼆维前缀和(medium)

​编辑总结:

1. 寻找数组的中⼼下标(easy)

解析:

1.暴力:

2.前缀和

总结:

2. 除⾃⾝以外数组的乘积(medium)

解析:

1.暴力:

2.前缀和

总结:

3. 和为 k 的⼦数组(medium)

解析:

1.暴力:

2.优化,前缀和

总结:

4. 和可被 K 整除的⼦数组(medium)

解析:

1.暴力:

2.优化:前缀和

5. 连续数组(medium)

解析:

1.暴力:

2.优化:前缀和

细节问题:

总结:

6. 矩阵区域和(medium)

解析:

1.暴力:

2.优化:前缀和矩阵

总结:


前缀和

前缀和题目对于我来说,相对比较难,那么总结相对更加全面。

前缀和就相当于小的动态规划,如果你提前学过一点动态规划,肯定看的出来,前缀和已经和动态规划大差不差,但是更容易能想到,可是难的题目还是会很难,简单的题目一眼就知道是利用前缀和。

那么再开始之前先来两道模板题,了解一下什么是前缀和

1. 【模板】⼀维前缀和(easy)

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    long long n,q;cin>>n>>q;
    vector<long long> ret(n+1);
    vector<long long> dp(n+1);
    // 1.读入数据
    for(int i=1;i<=n;i++) 
        cin>>ret[i];

    //2.计算前缀和
    for(int i=1;i<=n;i++)
        dp[i]=dp[i-1]+ret[i];
    
    //3.使用前缀和数组
    int l,r;
    while(q--)
    {
        cin>>l>>r;
        cout<<dp[r]-dp[l-1]<<endl;
    }

    return 0;
}

总结:

可以看出,前缀和就是要求出 前缀和数组 ret数组第i位的值的时候,可以通过它的前一位和nums[i],来得出当前的值。

2. 【模板】⼆维前缀和(medium)

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n, m, q; cin >> n >> m >> q;
    //1.读入数据
vector<vector<long long>> ret(n + 1, vector<long long>(m + 1));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> ret[i][j];

//2.创建前缀和
vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + ret[i][j];

//3.使用前缀和矩阵
    while(q--)
    {
        int x1,x2,y1,y2;cin>>x1>>y1>>x2>>y2;
        long long ans=0;
        ans=dp[x2][y2]-(dp[x2][y1-1]+dp[x1-1][y2]-dp[x1-1][y1-1]);
        cout<<ans<<endl;
    }

    return 0;
}

总结:

二维数组矩阵求前缀和:
1.因为ret跟dp都是从1开始的下标,那么就先让ret读入数据

2.读入后考虑dp的前缀和,dp[i][j] 就等于i行i列前面ret所有数据的和
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + ret[i][j];

3.使用前缀和数组,这题由于原数组的下标就是从1开始的,那么,x1 y1 x2 y2 就是原下标,直接进行操作就ok,考虑对数组元素的相减,不重复,不漏

总结:

前缀和可以就分三步进行:

1.读入数据

2.计算前缀和

3.使用前缀和数组

了解前缀和基本信息后,就可以上eg:

前缀和,就是通过前面已经求出来的数组的值,不需要再重新求一边,可以通过上次的结果+nums[i][j] 的值得到dp[i][j]该前缀和的值。

1. 寻找数组的中⼼下标(easy)

解析:

1.暴力:

肯定超时,如果只是对左右两边进行分别相加,那么到得出结果,时间复杂度肯定在O(N^2);

2.前缀和

那么对于求出前缀 跟 后缀分别相等的情况下,返回中心元素的下标
那么就要分别求出前缀和跟后缀和。然后进行比较。
细节问题:
求前缀和,那么ret1数组就要留一个ret1[0] = 0 就要多开一个刚空间,从下标1开始往后求
求后缀和,从下标n开始,那么就要跟前缀和对齐,到下标1结束,那么n的后面就要有下标为n+1的格子,那么实际上就要开n+2个空间
进行对比的时候,也都是从1~n,ret[i]进行比较,如果相等就返回下标-1
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] 表示。

数组特性就是分别是
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)

这题前缀和有点难想上去,但是想通了确实是豁然开朗。将出现过的数组存入hash表里,对他进行查找如果在这之前有出现过sum-k的值,就说明存在满足条件的子数组。

解析:

1.暴力:

就是遍历数组,然后每次都是从头开始相加,如果遇到大于K的就返回右移,重新开始相加

2.优化,前缀和

这题有点难想,一定要多思考,多花些时间
数组总和是sum[0~i] ,那么每次都要在这个数组里面找子数组和为k,那么反过来,就是要找和为sum-k 的子数组,如果hash表里存在,就说明,有满足条件的子数组,并且将能够满足的次数全都加到ret内,最后每次都将这个数组的和存入hash内,来更新数组的长度和hash的内容。
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

4. 和可被 K 整除的⼦数组(medium)

蓝桥杯原题~

解析:

1.暴力:

暴力就是变脸整个数组,然后查找每一个子数组的和来%k,这样时间复杂度太高,绝对过不了

2.优化:前缀和

先补充两个小知识点:
1).同余定理:
(a - b) % p = k……0 , 那么就有 a % p = b % p;
eg:(26 - 12) % 7 = 2……0 , 就是 26 % 7 = 12 % 7 = 5;
下面是取余的本质:
2) 在语言中,修正负数%正数的结果
负数 % 正数 = 负数
那么就让它扩大一倍在进行 % 运算
a % p -> (a % p + p) % p
那么解法二:前缀和 + 哈希表
翻译过来就是,在[0,i-1]区间内,找到有多少个前缀和的余数等于 (sum % k + k) % k
此时依然要运用一个hash表,hash<int,int> 分别存入余数+次数
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)

解析:

1.暴力:

前面已经做了很多题了,已经明白这种题如果上去就暴力肯定超时,但是仍然要从暴力往优化考虑;

2.优化:前缀和

这题如果只是按照题意上去写的话,确实是一道很难的题,找到0和1相同数目的最长子数组,光就考虑0和1的个数就很复杂。
但是如果将所有0改成 -1,那么题目意思就变得跟我们上一道题,一模一样,找出子数组最长和为0的长度,那么就很容易确定下来。

细节问题:

1)哈希表里存什么?
hash<int,int> 存前缀和 + 下标
这里不能跟上题一样存前缀和 + 出现的次数,因为这题要求最大长度,那么肯定是要用ret 跟 下标相减来进行比较。
2)什么时候存入哈希表?
使用完之后,丢进哈希表
3)如果有重复的<sum , i> 怎么存?
那么就证明重复的,只会让j越来越靠后,所以就不管他就ok,只存下只开始的一对
4)默认前缀和为0,怎么存?
hash[0] = -1,要从下标-1,开始存
5)长度怎么算?
那么就是i - j + 1 - 1 = i - j ,通过数组下标可以知道。
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)

题目还是比较简单理解的,就是求出在mat[i][j] 元素的k 的范围内,然后求出范围内所有元素的和。

解析:

1.暴力:

如果暴力遍历整个矩阵,然后每次求一个范围k内的值,那要O(N^3)

2.优化:前缀和矩阵

分三步:
1)输入数据
2)构造前缀和矩阵
3)使用前缀和矩阵
跟模板题类似,只需要找到下标对应的关系,真的是比较简单的一道题。
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,减去包含重复的元素即可。

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


原文地址:https://blog.csdn.net/2301_80636070/article/details/142319196

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!