前缀和算法：算法秘籍下的数据预言家

✨✨✨学习的道路很枯燥，希望我们能并肩走下来!

文章目录

前言

一. 前缀和算法的介绍

二、前缀和例题

2.1 【模版】前缀和

2.2 【模板】二维前缀和

2.3 寻找数组的中间下标

2.4 除自身以外数组的乘积

2.5 和为k的子数组

2.6 和可被k整除的子数组

2.7 连续数组

2.8 矩阵区域和

总结

前言

本篇详细介绍了前缀和算法的使用，让使用者了解前缀和，而不是仅仅停留在表面，文章可能出现错误，如有请在评论区指正，让我们一起交流，共同进步！

一. 前缀和算法的介绍

前缀和算法是一种用空间换时间的算法，他常常用于解决某些题目或者作为某些高级算法的组成部分。

例如：让你求某个矩阵（一维）的子矩阵的最大值，如果使用暴力解法它的时间复杂度将会是O(n^2) ，但如果使用该算法就可以使其时间复杂度降低一个维度也就是O(N).

前缀和是从 nums 数组中的第 0 位置开始累加，到第 𝑖位置的累加结果，我们常把这个结果保存到数组 Sum 中，记为 Sum[i]。

前缀和算法的本质是一个简单动态规划

接下来我们使用一些例题来介绍一下

二、前缀和例题

2.1 【模版】前缀和

牛客网—【模版】前缀和

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

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

    //2. 预处理出来个前缀和数组
    vector<long long> dp(n+1); //防止溢出
    for(int i = 1;i<=n;i++) dp[i] = dp[i-1]+arr[i];

    //3.使用前缀和数组
    int l = 0, r = 0;
    while(q--)
    {
        cin>>l>>r;
        cout<<dp[r]-dp[l-1]<<endl;
    }
    return 0;

}

2.2 【模板】二维前缀和

牛客网—【模版】二维前缀和

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

int main() {
    int n,m,q;
    cin>>n>>m>>q;
    vector<vector<int>> arr(n+1,vector<int>(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 = 0,y1 = 0,x2 = 0 ,y2 = 0;
    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;
}

2.3 寻找数组的中间下标

724. 寻找数组的中心下标 - 力扣（LeetCode）

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n), g(n);

        //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];
        //2. 使用
        for(int i = 0;i<n;i++)
            if(f[i] == g[i]) 
                return i;

        return -1;

    }
};

2.4 除自身以外数组的乘积

238. 除自身以外数组的乘积 - 力扣（LeetCode）

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

        return ret;
    }
};

2.5 和为k的子数组

560. 和为 K 的子数组 - 力扣（LeetCode）

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

2.6 和可被k整除的子数组

974. 和可被 K 整除的子数组 - 力扣（LeetCode）

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        hash[0 % k] = 1; //0 这个数的余数

        int sum = 0, ret = 0;
        for(auto& x : nums)
        {
            sum+=x; //算出当前位置的前缀和
            if(hash.count((sum%k+k)%k)) ret+=hash[(sum%k+k)%k]; //修正后的余数+统计结果
            hash[(sum%k+k)%k]++;
        }
        return ret;
    }
};

2.7 连续数组

525. 连续数组 - 力扣（LeetCode）

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int,int> hash;
        hash[0] = -1; //默认有一个前缀和为0的情况

        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;

    }
};

2.8 矩阵区域和

1314. 矩阵区域和 - 力扣（LeetCode）

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        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] - dp[i-1][j-1] + mat[i-1][j-1];

        vector<vector<int>> answer(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;
                int y1 = max(0,j-k)+1;
                int x2 = min(m-1,i+k)+1;
                int y2 = min(n-1,j+k)+1;
                answer[i][j] = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
            }
        return answer;

    }
};