【算法笔记】前缀和算法原理深度剖析（超全详细版）

【算法笔记】前缀和算法原理深度剖析（超全详细版）

🔥个人主页：大白的编程日记

🔥专栏：算法笔记

---

前言

哈喽，各位小伙伴大家好！上期我们讲了二分算法。今天我们来讲前缀和的算法原理。话不多说，咱们进入正题！向大厂冲锋！

一.一维前缀和

1.1题目

• 题目:【模板】前缀和
  

1.2算法原理解析

我们根据前缀和算法就可以快速求出区间和。

为了防止越界，我们要让前缀和数组下标从1开始。

1.3代码实现

#include <iostream>
#include<vector>
using namespace std;
int main() 
{int n,q;cin>>n>>q;vector<long long> dp(n+1);//多开一个节点防止越界int tmp=0;for(int i=1;i<=n;i++){cin>>dp[i];}for(int i=1;i<=n;i++){dp[i]+=dp[i-1];}int l,r;while(q--){cin>>l>>r;cout<<dp[r]-dp[l-1]<<endl;}
}
// 64 位输出请用 printf("%lld")

二.二维前缀和

2.1题目

• 题目:二维前缀和

2.2算法原理解析

2.3下标映射

2.4初始化问题

如果用到两个前缀和区间求某区间的和
我们初始化的值并不重要。

• 验证
  
  

2.5代码实现

#include <iostream>
#include<vector>
using namespace std;int main()
{int n, m, q;cin >> n >> m >> q;vector<vector<long long>> arr(n,vector<long long>(m));for (int i = 0; i <n; i++){for (int j = 0; 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][j - 1]+dp[i-1][j]-dp[i-1][j-1]+arr[i-1][j-1];}}while (q--){int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;long long sum=0;sum=dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1];cout<<sum<<endl;}
}

三.寻找数组的中心下标

3.1题目

• 题目：寻找数组的中心下标
  

3.2思路分析

这里我们借助前缀和数组和后缀和数组即可快速判断中心下标。

3.3代码实现

class Solution {
public:int pivotIndex(vector<int>& nums){int n=nums.size();vector<int> f(n),g(n);for(int i=1;i<n;i++)//前缀和数组{f[i]=nums[i-1]+f[i-1];}for(int i=n-2;i>=0;i--)//后缀和数组{g[i]=g[i+1]+nums[i+1];}for(int i=0;i<n;i++)//判断{if(f[i]==g[i]){return i;}}return -1;}
};

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

4.1题目

• 题目：除自身以外数组的乘积
  

4.2思路分析

4.3总结

4.4代码实现

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

五.和为k的子数组

5.1题目

• 题目：和为k的子数组
  

5.2思路分析

5.3代码实现

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int> hash;hash[0]=1;//整个区间和为kint sum=0,ret=0;for(auto e:nums){sum+=e;//计算前缀和if(hash.count(sum-k))//统计和为sum-k区间个数{ret+=hash[sum-k];}hash[sum]++;//填入前缀和信息}return ret;}
};

六.和可被k整除的子数组

6.1题目

• 题目：和可被k整除的子数组
  

6.4思路分析

6.3代码实现

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int,int> hash;hash[0]=1;//整个区间和为kint sum=0,ret=0;for(auto e:nums){sum+=e;//计算前缀和if(hash.count((sum%k+k)%k))//统计和为被k整除区间个数负数修正{ret+=hash[(sum%k+k)%k];}hash[(sum%k+k)%k]++;//填入前缀和%k信息}//(a-b)%p==a%p==b%p同余定理return ret;}
};

七.连续数组

7.1题目

• 题目：连续数组
  

7.1思路分析

7.3代码实现

class Solution {
public:int findMaxLength(vector<int>& nums){unordered_map<int,int> hash;hash[0]=-1;int sum=0,len=0;for(int i=0;i<nums.size();i++){sum+=(nums[i]==0?-1:1);//0就变成-1；if(hash.count(sum-0)){len=max(len,i-hash[sum]);//更新长度}else//相同的前缀和不更新{hash[sum]=i;//更新哈希表前缀和信息}}return len;}
};

八.矩阵区域和

8.1题目

• 题目：矩阵区域和
  

8.2思路分析

8.3代码实现

class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k){int m=mat.size(),n=mat[0].size();vector<vector<int>> arr(m+1,vector<int>(n+1));for(int i=1;i<m+1;i++)//处理前缀和数组{for(int j=1;j<n+1;j++){arr[i][j]=arr[i][j-1]+arr[i-1][j]-arr[i-1][j-1]+mat[i-1][j-1];}}vector<vector<int>> arr1(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 x2=min(m-1,i+k)+1;int y1=max(0,j-k)+1;int y2=min(n-1,j+k)+1;//计算下标 +1映射dp数组arr1[i][j]=arr[x2][y2]-arr[x2][y1-1]-arr[x1-1][y2]+arr[x1-1][y1-1];}}return arr1;}
};

后言

这就是前缀和算法原理的深度剖析。大家自己好好消化理解。今天 就分享到这，感谢各位大耐心垂阅！咱们下期见！拜拜~