leetcode算法之前缀和

1.DP34[模板]一维前缀和

一维前缀和

#include 
#include 
using namespace std;

int main()
{
    int n,q;
    cin>>n>>q;
    vector<long long> v(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    //1.维护一个前缀和数组
    vector<long long> dp(n+1);
    for(int i=1;i<=n;i++)
    {
        dp[i]=dp[i-1]+v[i];
    }
    //2.使用前缀和数组
    int l,r;
    while(q--)
    {
        cin>>l>>r;
        cout<<dp[r]-dp[l-1]<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

2.DP35[模板]二维前缀和

二维前缀和

#include 
#include 
using namespace std;

int main()
{
    int n,m,q;
    cin>>n>>m>>q;
    vector<vector<long long>>arr(n+1,vector<long long>(m+1));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>arr[i][j];
        }
    }
    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]+arr[i][j]-dp[i-1][j-1];
        }
    }
    int x1,y1,x2,y2;
    while(q--)
    {
        cin>>x1>>y1>>x2>>y2;
        cout<<dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

3.寻找数组的中心下标

寻找数组的中心下标

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        //1.维护一个前缀和和后缀和数组
        vector<int> f(n);
        for(int i=1;i<n;i++)
        {
            f[i] = f[i-1]+nums[i-1];
        }
        vector<int> g(n);
        for(int i=n-2;i>=0;i--)
        {
            g[i] = g[i+1]+nums[i+1];
        }
        //2.使用前缀和和后缀和数组
        for(int i=0;i<n;i++)
        {
            if(f[i] == g[i])
            {
                return i;
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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

除自身以外数组的乘积

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);
        f[0] = 1;
        for(int i=1;i<n;i++)
        {
            f[i] = f[i-1]*nums[i-1];
        }
        vector<int> g(n);
        g[n-1] = 1;
        for(int i = n-2;i>=0;i--)
        {
            g[i] = g[i+1]*nums[i+1];
        }
        vector<int> ret(n);
        for(int i=0;i<n;i++)
        {
            ret[i] = f[i]*g[i];
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

5.和为K的子数组

和为K的子数组

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        hash[0] = 1;

        int sum = 0,ret = 0;
        for(auto x:nums)
        {
            sum+=x;
            if(hash.count(sum-k)) ret+=hash[sum-k];
            hash[sum]++;
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

6.和可被K整除的子数组

和可被K整除的子数组

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        //前缀和+哈希表
        unordered_map<int,int> hash;
        hash[0%k] = 1;

        int ret = 0,sum = 0;
        for(auto x:nums)
        {
            sum+=x;
            int r = (sum%k+k)%k;
            if(hash.count(r)) ret+=hash[r];
            hash[r]++;
        }
        return ret;
    }
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

7.连续数组

连续数组

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        //前缀和+哈希表
        //哈希表里面存储的是前缀和和对应的下标
        unordered_map<int,int> hash;
        hash[0] = -1;

        int sum = 0,ret = 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

8.矩阵区域和

矩阵区域和

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(),n = mat[0].size();
        //二维前缀和+dp数组
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        for(int i = 1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j] = dp[i-1][j]+dp[i][j-1]+mat[i-1][j-1]-dp[i-1][j-1];
            }
        }
        //使用前缀和数组dp
        vector<vector<int>> ret(m,vector<int>(n));
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                int x1 = max(0,i-k)+1,y1=max(0,j-k)+1;
                int x2 = min(m-1,i+k)+1,y2 = min(n-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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27