【算法笔记】前缀和算法原理深度剖析（超全详细版）
【算法笔记】前缀和算法原理深度剖析（超全详细版）
🔥个人主页：大白的编程日记
🔥专栏：算法笔记
文章目录
- 【算法笔记】前缀和算法原理深度剖析（超全详细版）
前言
哈喽，各位小伙伴大家好！上期我们讲了二分算法。今天我们来讲前缀和的算法原理。话不多说，咱们进入正题！向大厂冲锋！
一.一维前缀和
1.1题目
- 题目:【模板】前缀和
1.2算法原理解析
我们根据前缀和算法就可以快速求出区间和。
为了防止越界，我们要让前缀和数组下标从1开始。
1.3代码实现
#include #includeusing 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 #includeusing 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;//整个区间和为k int 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;//整个区间和为k int 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; }};
后言
这就是前缀和算法原理的深度剖析。大家自己好好消化理解。今天 就分享到这，感谢各位大耐心垂阅！咱们下期见！拜拜~
