【算法】前缀和经典例题

1.DP34 【模板】前缀和

1.1算法原理

• 前缀和–快速求出数组中某一个连续区间的和

1.预处理出来一个前缀和数组

⽤ dp[i] 表⽰： [1, i] 区间内所有元素的和，那么 dp[i - 1] ⾥⾯存的就是 [1,
i - 1] 区间内所有元素的和，那么：可得递推公式： dp[i] = dp[i - 1] + arr[i] ；

2.使用前缀和数组

当询问的区间是 [l, r] 时：区间内所有元素的和为： dp[r] - dp[l - 1]

细节问题:为什么下标要从1开始计数?

为了处理使用前缀和数组时的边界情况,若区间[l,r]从0开始,那么dp[r] - dp[l - 1]中dp[l - 1]索引为-1越界,所以设定从下标为1开始,并且添加虚拟节点下标为0处的值为0,这样既避免了越界情况又防止影响前缀和的结果

时间复杂度为预处理前缀和数组的O(n)+使用前缀和数组计算的O(q)

#include <iostream>
#include <vector>
using namespace std;int main() {//1.读入数据int n,m;cin>>n>>m;//因为从下标为1处开始计算,所以要多出一个位置并设置为0vector<long long> vec(n+1),dp(n+1);//设置为long long防止处理前缀和数组加法时溢出for(int i=1;i<=n;i++) cin>>vec[i];//2.预处理一个前缀和数组for(int i=1;i<=n;i++) dp[i]=dp[i-1]+vec[i];while(m--){int l,r;cin>>l>>r;//3.使用前缀和数组计算cout<<dp[r]-dp[l-1]<<endl;}return 0;
}

2.DP35 【模板】二维前缀和

2.1算法原理

• 前缀和

算法思路:
类⽐于⼀维数组的形式，如果我们能处理出来从 [0, 0] 位置到 [i, j] 位置这⽚区域内所有元素的累加和，就可以在 O(1) 的时间内，搞定矩阵内任意区域内所有元素的累加和

1.预处理出来一个前缀和矩阵

这⾥就要⽤到⼀维数组⾥⾯的拓展知识，我们要在矩阵的最上⾯和最左边添加上⼀⾏和⼀列0，这样我们就可以省去⾮常多的边界条件的处理处理后的矩阵就像这样：

这样，我们填写前缀和矩阵数组的时候，下标直接从 1 开始，能⼤胆使⽤ i - 1 , j - 1 位置的值。

dp[i][j]表示从[1,1]位置到[i,j]位置,这段区间内所有元素的和

将矩阵分为4个区域来相加,由于B和C不好直接计算,可以先加上A一起计算最后会多一个A再减去

2.使用前缀和矩阵

为了计算子矩阵之和,一样将矩阵划分为四个区域小矩阵,同样将A与B,A与C一起计算最后会多减去一个A,补上一个即可.
细节注意:计算的下标应为x1-1和y1-1,因为最终结果是要包含x1,y1位置处元素的

时间复杂度为预处理前缀和数组的O(n*m)+使用前缀和数组计算的O(q)

#include <iostream>
#include <vector>
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]=arr[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];}}//使用前缀和矩阵计算while(q--){int x1,x2,y1,y2;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;
}

3. (724.) 寻找数组的中⼼下标

3.1算法原理

前缀和:

已知前缀和思想是用一个数组提前存储某个区间的值,一般是从0开始到n-1位置,只要掌握了核心思想就可以产生变化,本题是求中心下标,要求下标左边元素之和等于右边元素之和,那么就可以预处理一个前缀和+后缀和,再判断两个数组相同下标处元素值是否相同

我们不需要计算中心下标的元素值,以前缀和数组为例f(i-1)实际上求的是[0,i-2]的值

题目要求优先返回最左边的值,采取从[0,n-1]遍历的方法求解下标

细节问题:

1.边界问题
总共n个元素,区间[0,n-1],当求前缀和f(0)=f(-1)+nums(-1)时和求后缀和g(n-1)=g(n)+f(n)时都是越界访问且值是随机的,我们要判断条件f(0)=0,g(n-1)=0
2.求前缀和数组的顺序是从左往右,求后缀和的顺序是从右往左

class Solution {
public:int pivotIndex(vector<int>& nums) {int n=nums.size();vector<long long> f(n),g(n);//预处理前缀和数组,下标从1开始遍历可以直接防止越界for(int i=0;i<n;i++) {if(i==0) f[i]=0;else f[i]=f[i-1]+nums[i-1];}//预处理后缀和数组,下标从n-2开始遍历可以直接防止越界for(int i=n-1;i>=0;i--) {if(i==n-1) g[i]=0;else 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. (238.)除⾃⾝以外数组的乘积

4.1算法原理

与上题相同,不用计算当前位置值,从当前位置i计算[0,i-1]区间的所有乘积和[i+1,n-1]区间内的所有乘积,再将两个区间得出的乘积再相乘
本题将前缀和,后缀和的计算改为计算前缀积和后缀积



同样要注意边界处理,要把g[n-1]和f[0]处元素置1,这样才不会改变乘积,与上题区别.
最后返回的时候开辟一个数组来记录前缀积和后缀积的乘积

前缀和算法的本质就是预处理+空间换时间

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n=nums.size();vector<long long> f(n),g(n);//预处理前缀积数组,边界情况要处理成1才不会影响乘积for(int i=0;i<n;i++) {if(i==0) f[i]=1;else f[i]=f[i-1]*nums[i-1];}//预处理后缀积数组for(int i=n-1;i>=0;i--) {if(i==n-1) g[i]=1;else 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;}
};

5. (560.)和为 K 的⼦数组

5.1算法原理

1.暴力解法:
采用枚举法,从开始位置一直向后计算乘积,注意找到和为k后还要继续往后计算,因为有可能为负数,时间复杂度为O(n^2)
不能用双指针来优化,因为不具有单调性

2.前缀和+双指针

1.设 i 为数组中的任意位置，⽤ sum[i] 表⽰ [0, i] 区间内所有元素的和
2.问题转化:
想知道有多少个「以 i 为结尾的和为 k 的⼦数组」，就要找到有多少个起始位置为 x0, x1, x2… 使得 [x, i] 区间内的所有元素的和为 k(也可以推广到[0,i]) 。那么 [0, x] 区间内的和就是sum[i] - k 了。于是问题就变成：
找到在[0,x]即推广到 [0, i - 1] 区间内(等于k的子数组至少在[i-1,i]之间)，有多少前缀和等于 sum[i] - k 的即可。

细节问题:
1.前缀和加入哈希表的时机:

不能将所有前缀和计算完后才加入哈希表,这样会导致i位置的前缀和计算重复.应该计算i位置之前,哈希表中只保存[0,i-]位置的前缀和

2.不用真的创建一个前缀和数组

用一个变量sum标记前一个位置的前缀和即可.前缀和计算公式一般为dp[i]=dp[i-1]+nums[i]将其中dp[i-1]换为sum即可

3.特殊情况:如果整个前缀和=k

由于在[x,i]之间所有元素和为k的问题转化为[0,x]即[0,i-1]区间内有多少前缀和等于sum[i] - k,两个关系相互依赖,互为充分必要条件
整个数组前缀和为k即[0,i]区间内,那么下标0元素之前的前缀和必须为为sum[i] - k,对应的hash[0]设为1

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int n=nums.size();unordered_map<int,int> hash;// 统计前缀和出现的次数int sum=0,ret=0;//判断特殊情况初始化hash[0]=1;for(int i=0;i<n;i++){sum+=nums[i];// 计算当前位置的前缀和if(hash.count(sum-k)) ret+=hash[sum-k];// 统计个数hash[sum]++;}return ret;}
};

6. (974.) 和可被 K 整除的⼦数组

6.1算法原理

同余定理

如果 (a - b) % n == 0 ，那么我们可以得到⼀个结论： a % n == b % n 。⽤⽂字叙述就是，如果两个数相减的差能被 n 整除，那么这两个数对 n 取模的结果相同。

C++中负数取模的结果及修正

1.c++ 中关于负数的取模运算，结果是「把负数当成正数，取模之后的结果加上⼀个负号」。例如： -1 % 3 = -(1 % 3) = -1
2.因为有负数，为了防⽌发⽣「出现负数」的结果，以 (a % n + n) % n 的形式输出保证为正。例如： -1 % 3 = (-1 % 3 + 3) % 3 = 2,当原始结果为正时后+的n可以被消去,为负时可以被修正

前缀和+哈希表,与和为k的子数组思路相同进行问题转化

设 i 为数组中的任意位置，⽤ sum[i] 表⽰ [0, i] 区间内所有元素的和。
1.想知道有多少个以 i 为结尾的可被 k 整除的⼦数组，就要找到有多少个起始位置为 x1, x2, x3… 使得 [x, i] 区间内的所有元素的和可被 k 整除。
2.设 [0, x - 1] 区间内所有元素之和等于 a ， [0, i] 区间内所有元素的和等于 b ，可得(b - a) % k == 0
3.转化问题:
由同余定理可得， [0, x - 1] 区间与 [0, i] 区间内的前缀和同余。于是问题就变成：找到在 [0, i - 1] 区间内，有多少前缀和的余数等于 sum[i] % k(记得修正) 的即可。

不需要真的创建并初始化一个前缀和数组,只关心在i位置之前有多少个前缀和的余数等于(sum[i]%k+k)%k 。因此，我们仅需⽤⼀个哈希表，⼀边求当前位置的前缀和，⼀边存下之前每⼀种前缀和余数出现的次数。

细节处理:

1.特殊边界情况:
当整个数组元素的可被k整除,由于我们进行了问题转化的求解把区间划分为[0,x]和[x,i], sum[i] 表⽰ [0, i] 区间内所有元素的和.当[x,i]内所有元素能被k整除时,由同余公式得sum[i]与[0.x]内元素和除k的余数相同,既然整个数组都可被k整除,那么此时[0,0]和[0,i]区间内元素余数相同且hash[0%k]必须存在且为1
2.顺序问题
sum[i]前缀和内被划分为两个区间如上图所示,入哈希表的不包括i位置值,所以不能全部计算完后一起加入哈希表,得边计算边加入,避免重复计算

lass Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int,int> hash;//处理整个数组都可以被k整除的情况hash[0%k]=1;int sum=0,ret=0;for(auto e:nums){sum+=e;int r=(sum%k+k)%k;// 算出当前位置的前缀和if(hash.count(r)) ret+=hash[r];// 修正后的余数hash[r]++;}return ret;}
};

7. (525.) 连续数组

7.1算法原理

1.将所有的0修改成-1,该题转化成找出最长的子数组使所有元素的和为0,与第560题和为k的子数组思路相似
2.想知道最⼤的「以 i 为结尾的和为 0 的⼦数组」，就要找到从左往右第⼀个 x1 使得 [x1, i]区间内的所有元素的和为 0 。那么 [0, x1 - 1] 区间内的和就是 sum[i] 了。于是问题就变成：
找到在 [0, i - 1] 区间内，第⼀次出现 sum[i] 的位置即可(此时后区间的子数组最长)

细节注意:

1.哈希表中存什么
由于我们计算的不再是出现次数而是长度,所以hash<int,int>中第一个位置存的前缀和,第二个位置存下标方便后续计算长度

2.使用完一个前缀和后就放进哈希表,与560题一样,数组被划分为两个区间,前区间为所求前缀和,后区间为所求目标数组长度,所以当前位置不计算而是计算当前位置之前的前缀和.

3.如果有重复的<sum,i>,只保留前面的一对,这样可使后区间所求目标子数组最长

4.默认前缀和即整个数组为0的情况,由于hash中第二个值存的是下标,那么hash[0]=-1

5.如何计算长度,如上图所示i-j+1-1=i-j

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;//确保只记录sum出现的最小位置,并更新长度if(hash.count(sum)) ret=max(ret,i-hash[sum]);else hash[sum]=i;} return ret;}
};

8. (1314.) 矩阵区域和

返回矩阵中的每个元素,是原矩阵中对应元素往上下左右外扩k个位置在矩形区域内所围成的和

8.1算法原理

• 二维前缀和

与二维前缀和模板不同的是,模板的下标是从(1,1)位置开始预处理前缀和数组的,该题是从(0,0)位置,但是从该位置进行计算会造成越界问题,所以在返回矩阵区域和时的前缀和数组要进行下标的转换,还是要让前缀和数组从下标1处开始计算才能避免复杂的边界情况讨论,这就要求计算时使用原数组下标时比前缀和数组少1
预处理前缀和数组如下:

下标的映射关系如下:

mat为题目给定数组,dp为我们预处理的前缀和数组(要预留一行和一列0作为边界条件判断),ans是要返回的矩阵区域和

计算前缀区域和时要知道区域内左上角和右下角的坐标,一般模板如下

本题因为要扩展区域,所以要限制求左上角和右下角的范围

求得之后正常带入前缀和公式中进行计算即可

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>>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[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1];}}return ret;}
};