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

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

文章目录

前言

一. 前缀和算法的介绍

二、前缀和例题

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