目录
前言
本篇博客是对前缀和算法一部分经典题目的整理与每道题很详细的思考与题解过程，相信大家看完能对前缀和算法类型的相关问题有一定的理解和掌握(。・∀・)ノ
1.（模板）一维前缀和
题目解释：
算法原理：前缀和
注意下面我们的询问q次和查询m次是一样的意思
解法一：暴力解法->模拟 时间复杂度：O（n*q）n和q的范围决定这个解法肯定会超时
解法二：前缀和（用于需要快速求出数组中某一连续区间的和相关问题）
步骤：
第一步：预处理出来一个前缀和数组
dp[i]表示：[1, i]区间内所有元素的和
dp[ i ] = dp[ i - 1 ] + arr[ i ]
第二步： 使用前缀和数组
要计算数组[L , r]范围之和就相当于计算dp[ r ] - dp[ L - 1 ] （本质：间接求和）
两步下来的时间复杂度是：O（q+n），q为q次询问所需时间，n为遍历一遍求和所需时间
处理细节：为什么下标要从1开始计数？
因为如果从0开始，当出现要求[0,r]这种情况时，会出现dp[-1]越界访问了，这样还得花时间去处理边界情况，下标从1开始的话，上面这种情况不会出现，最小也只会是dp[0]，而dp[0]初始化数组时为0不会变，不会影响后面的求和
解题代码：c++
#include <iostream>
#include<vector>
using namespace std;
int main()
{
//前置工作:读入数据
int n,q;
cin>>n>>q;
//大小为n+1的数组
vector<int> arr(n+1);
for(int i=1;i<=n;i++)
{
cin>>arr[i];
}
//采用前缀和算法
//1.现预处理出来一个前缀和数组
//根据数组中元素的范围，相加之和使用int是很可能由溢出情况的
//所以这里采用long long类型数组
vector<long long> dp(n+1);
for(int i=1;i<=n;i++)
{
dp[i]=dp[i-1]+arr[i];
}
//2.使用前缀和数组
int l,r;
//询问q次
while(q--)
{
cin>>l>>r;
//使用前缀和数组求得输出结果
cout<<dp[r]-dp[l-1]<<endl;
}
return 0;
}2.（模板）二维前缀和
题目解释：
算法原理：二维前缀和
解法一：暴力->模拟 最坏是每次询问都要遍历一遍数组：时间复杂度O（n* m *q）
解法二：前缀和 时间复杂度O（q）
步骤：
1.预处理出来一个前缀和矩阵
我们这里的dp[i][j]表示；从[1][1]位置到[i][j]位置，这段区间里面所有元素的和
关于求dp[i][j]，我们很容易想到的是依次遍历去求和，但是这样造成时间上的浪费是比较高的，我们可以通过划分这段区域的方式来进行求和拆解，将这段和拆解为以下四个区域的和
进而我们可以将dp[i][j]求和转换为求A+B+C+D（各区域的和加起来就是dp[i][j]），而我们会发现在求解过程中，我们很难去单独求得C、B区域的和，所以我们又可以转换成求（A+B）+(A+C)+D-A，因为A和B构成的区域就是从[1][1]到[i-1][j]所有元素的和，也就是dp[i-1][j]，而C和A构成的区域就是从[1][1]到[i][j-1]所有元素的和，也就是dp[i][j-1]，这样算会多出一个A，所以我们在此基础上减一个A区域的和(dp[i-1][j-1])，再加上D，D就是在我们矩阵中arr[i][j]位置的元素值
综上：dp[i][j] = A+B+C+D=(A+B)+(A+C)-A+D=dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j]
这样求得的dp[i][j]的时间复杂度就是O（1）
2.使用前缀和矩阵
我们要求[x1][y1]到[x2][y2]这段区域里面的和也可以拆分为ABCD四个区域进而求解
如图所示，我们要求的区域和就是D区域，和求dp[i][j]时雷同，我们可以反过来，用A+B+C+D-(A+B+C)来求得D，而A+B+C+D不就是我们的dp[x2][y2]么，同样的B、C区域和难求，我们就把它们分别和A结合进而得到D=dp[x2][y2] - (A+B) -(A+C) +A，A+B区域和就是dp[x1-1][y2]，A+B区域和就是dp[x2][y1-1]，A区域和是dp[x1-1][y1-1]
综上：[x1][y1]到[x2][y2]区域的和=D=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]
这里的时间复杂度也是O(1)
所以使用前缀和两步的时间复杂度都是O（1），只需要查询q次，也就是时间复杂度最终是O（q）
解题代码：c++
#include <iostream>
#include<vector>
using namespace std;
int main() {
//1.前置工作,读入数据
int n = 0, m = 0, q = 0;
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];
}
}
//2.预处理出来一个前缀和矩阵
//由于这里读入的数据可能很大，使用整型相加会有溢出的风险，所以我们这里使用long long类型
//的矩阵
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]-dp[i-1][j-1]+arr[i][j];
}
}
//3.使用前缀和矩阵
int x1=0,y1=0,x2=0,y2=0;
for(int i=0;i<q;i++)
{
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.寻找数组的中心下标
算法原理：一维前缀和
解法一：暴力枚举
解法二：前缀和
不要死记模板，要根据题意来得出递推公式
步骤：
预处理出dp数组
根据上图分析，我们可以基于i这个位置分离出前后两个前缀和数组dp，这样可以提高求和的效率
f：前缀和数组，f[i]表示[0 , i-1]区间内，所有元素的和
f[i] = f[i-1]+nums[i-1],因为f[i-1]中存着i-1前面所有元素的和
g：后缀和数组，g[i]表示[i+1 , nums.size()-1]区间内，所有元素的和
g[i] = g[i+1]+nums[i+1],因为g[i+1]中存着i+1前面所有元素的和
使用dp数组：使用f和g两数组
遍历一遍nums数组，其中当i位置满足f[i]=g[i]时，i为数组中心下标
细节问题：
a. 上面前后缀和数组都有越界访问的情况：
f[i-1]当i为0时，越界，所以我们得先对f(0)进行处理，而f(0)前面没有元素，所以f(0)=0
g[i+1]当i为nums.size()-1时，越界，所以我们得先对f(nums.size()-1)进行处理，而f(nums.size()-1后面没有元素，所以f(nums.size()-1)=0
b. 填两数组的顺序问题
f[i]依赖的是f[i-1]，所以得从左向右填
g[i]依赖的是g[i+1],所以得从右向左填
解题代码：c++
class Solution {
public:
int pivotIndex(vector<int>& nums)
{
//本题采用前缀和算法解题
//1.预处理出来一个前缀和数组
//本题特殊，我们得预处理出来前后两个缀和数组f和g
vector<int> f(nums.size());
vector<int> g(nums.size());
//首先我们先处理一下越界情况
f[0]=0,g[nums.size()-1]=0;
//从左往右填f
for(int i=1;i<nums.size();i++)
{
f[i]=f[i-1]+nums[i-1];
}
//从右往左填g
for(int i=nums.size()-2;i>=0;i--)
{
g[i]=g[i+1]+nums[i+1];
}
//2. 使用两个数组
for(int i=0;i<nums.size();i++)
{
//如果i位置的前缀和等于后缀和，说明i就是中心下标
if(f[i]==g[i])
{
return i;
}
}
return -1;
}
};4. 除自身以外数组的乘积
算法原理：一维前缀和
解法一：暴力解法，遍历两边数组解决，时间复杂度：O（n^2）
解法二：前缀和
和上一道题基本思想一模一样，都是要预处理出前后缀和数组，只不过我们这里应该是前后缀积（所以还是那句话，不要死记模板，要结合题目！！）
预处理出dp数组
根据上图分析，我们可以基于i这个位置分离出前后两个前缀积数组dp，这样可以提高求和的效率(用空间来换时间)
f：前缀积数组，f[i]表示[0 , i-1]区间内，所有元素的乘积
f[i] = f[i-1]*nums[i-1],因为f[i-1]中存着i-1前面所有元素的乘积
g：后缀积数组，g[i]表示[i+1 , nums.size()-1]区间内，所有元素的乘积
g[i] = g[i+1]*nums[i+1],因为g[i+1]中存着i+1前面所有元素的乘积
使用dp数组：使用f和g两数组
先创建一个与nums同样长度的答案ans数组，遍历一遍nums数组，其中i位置的元素除它之外的 所有元素的积就是f[ i ] * g[ i ]，也就是ans[i]=f[ i ] * g[ i ]
细节问题
f[0]=1,g[nums.size()-1]=1,因为这样一来1乘以任何数结果就是这个任何数，就代表前后缀积只有一个是存在的
解题代码：c++
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums)
{
//使用前缀和算法
//1. 预处理出前后缀和两数组
int n=nums.size();
vector<int> f(n);
vector<int> g(n);
//先处理一下边界情况
f[0]=1,g[n-1]=1;
//填表
//从左向右填f
for(int i=1;i<n;i++)
{
f[i]=f[i-1]*nums[i-1];
}
//从右向左填g
for(int i=n-2;i>=0;i--)
{
g[i]=g[i+1]*nums[i+1];
}
//使用两dp数组
vector<int> ans;
for(int i=0;i<n;i++)
{
ans.push_back(f[i]*g[i]);
}
return ans;
}
};5.和为k的子数组
算法原理：前缀和 + 哈希表
解法一：暴力解法——枚举 时间复杂度O（n^2）
通过上图中的演示，由于我们这题的元素是可能为0和负数的，所以left和right中间子数组也有机会满足条件，所以不能使用双指针的滑动窗口算法来优化
解法二：前缀和 + 哈希表
思路：
我们这个题目的要求对于前缀和sum数组来说，应该考虑的是以i位置为结尾的前面所有子数组，也就是题目的要求也被我们转换成在[0 , i-1]区间内，有多少个前缀和等于sum[i] - k，那这个前缀和在num位置处到i位置就是一个满足条件的子数组
但是如果我们还是需要遍历num的i，然后再在sum前缀和数组中遍历找到i位置，再向i前面遍历找前缀和，这样的时间复杂度都比暴力解法高了，所以我们得借助一个能统计前缀和出现次数的哈希表，在i位置直接从表里查出有多少前缀和满足sum[i] - k就行了
细节问题：
上面的思路二中的前缀和加入哈希表的时机是一处我们要考虑的细节，如果我们把所有的前缀和直接一次性加入到哈希表中是不行的，因为我们需要统计的是[0 , i -1]区间中满足条件的前缀和，所以正确的做法应该是在计算完在i位置有多少前缀和满足条件之前，哈希表中只保存[0 , i-1]位置的前缀和
不用真的创建一个前缀和数组
用一个变量sum来标记前一个位置的前缀和即可，也就是sum+=nums[i]就是该位置的前缀和
如果整个前缀和等于k呢？
此时如果i为0的话，其实应该去[0,-1]这个区间找前缀和为0的，但是没有这个区间，可是需要有前缀和为0，所以我们需要提前让hash[0]=1
解题代码：c++
class Solution {
public:
int subarraySum(vector<int>& nums, int k)
{
//哈希表来统计前缀和出现的次数
unordered_map<int,int> hash;
//先处理hash[0]=1
hash[0]=1;
//ret记录最终结果，sum表示i-1位置前缀和，一开始都是0
int sum=0,ret=0;
for(auto n:nums)
{
//先计算一下当前位置的前缀和
sum+=n;
//判断在这位置前缀和之前的前缀和是否有等于sum-k的前缀和
if(hash.count(sum-k))
{
ret+=hash[sum-k]; //统计个数
}
//将该位置的前缀和插入到哈希表中
hash[sum]++;
}
return ret;
}
};6.和可被k整除的子数组
是某一年蓝桥杯原题！！
算法原理：前缀和+哈希表
解法一：暴力解法
在解法二之前，我们需要补充两点额外的知识
2.c++，java中：负数%正数的结果以及修正
（也是借助上面的公式的）
解法二：前缀和+哈希表
如图分析可知：我们题目要求子数组的和能被k整除，那么我们需要让前缀和数组中：i位置前缀和减去i位置之前的前缀和就是子数组，这个差值要%k=0，那么由我们的同余定理可得，此时就只需要在i位置之前的前缀和中找到模上k的余数等于i位置前缀和模上k时的余数就好了，和我们上一题一样，不需要真正创建一个前缀和数组，直接用sum+=nums[i]就好了
而我们要注意的是，数组nums中的数是可能为负数的，所以根据我们的补充知识2，我们需要把问题转换成：
然后我们此题中哈希表中存储的应该是前缀和%k得到的余数，统计的就是在这个位置之前有多少余数等于sum%k取得的余数，然后就能得到有多少个满足条件的子数组了（实际取余的时候应是上面说的用(sum%k+k)%k）前面这段话中的sum%k只是表达取余的意思
其他细节问题就和我们上一题一样了
解题代码：c++
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k)
{
//使用前缀和+哈希表算法
//哈希表用来统计前缀和%k的余数
unordered_map<int,int> hash;
//处理um[0]=1的边界情况
hash[0]=1; //这里存的是0这个数的余数，0%任何数都是0
//需要sum来记录前缀和，以及ret记录有多少个子数组满足题意
int sum=0,ret=0;
for(auto num:nums)
{
sum+=num;
//这里注意nums中的值可能为负数，所以得进行修正处理（用补充知识2）
//使用(sum%k+k)%k来取余数
if(hash.count((sum%k+k)%k))
{
ret+=hash[(sum%k+k)%k]; //记录满足于sum%k取得的余数相等的余数
}
//在判断完这个位置之后，再将其取模后的余数放入哈希表中
hash[(sum%k+k)%k]++;
}
return ret;
}
};7.连续数组
算法原理：前缀和+哈希表
本题如果我们直接上来统计0、1的次数，这道题是非常困难的，当问题是这种0、1并且需要让一个子数组中的元素0、1个数相等时，我们可以转化一下问题：
转化：
将所有的0修改成-1
在子数组中，找出最长的子数组，使得子数组中所有元素的和为0
这样的话，算法原理不就和我们前面的那道和为k的子数组是一样的吗，只不过现在这里就是找和为0的子数组，所以我们就可以使用和为k的子数组这题的思想来解决这一道题
解法：前缀和 +哈希表
不过在写的时候，还是有不少细节和那道题不一样的
细节问题：
哈希表中的第一个k还是表示满足sum的前缀和，第二个v则应该是该前缀和的下标了
什么时候存入哈希表？
答：还是在计算完在i位置有多少前缀和满足条件之前，哈希表中只保存[0 , i-1]位置的前缀和，也就是在使用完之后再将这个sum丢入哈希表
如果有重复的满足条件的下标，该如何存
答：只保留前面的那个下标，这样求的子数组是较长的，也就是当i位置前面不存在满足条件的前缀和时，此时的i就是满足前缀和为当前sum的最前下标了
默认的前缀和为0的情况，如何存？也就是当整个数组前缀和就是0时
答：那我们本应该在0前面也就是-1位置找到与这个sum=0相等的sum，所以我们可以将hash[0]=-1，和那道题不一样的地方在于那道题是存次数（也就是hash[0]=1,表示sum=0时有一个前缀和满足），我们这里是表示这个满足的前缀和的下标是-1
长度应该怎么算？
答：假设我们此时在i位置前缀和sum，在前面的下标j处找到满足条件=sum的前缀和，那么i到j位置有i-j+1个元素，但注意，我们的满足元素为0的子数组应该是从j的下一个位置的元素开始到i的，也就是我们还需要i-j+1之后再-1（舍去j位置），也就是计算公式为i-j
解题代码：c++
class Solution {
public:
int findMaxLength(vector<int>& nums)
{
//前缀和+哈希表统计满足条件的前缀和下标的算法
//注意处理各种和那道题不一样的细节问题
//哈希表中v存的是满足条件前缀和所在的下标
unordered_map<int,int> hash;
hash[0]=-1;
int sum=0,ans=0;
for(int i=0;i<nums.size();i++)
{
//先将所有的0变成-1
if(nums[i]==0)
{
nums[i]=-1;
}
//沿用和为k的子数组的解题方法再注意细节问题
sum+=nums[i];
if(hash.count(sum))
{
ans=max(ans,i-hash[sum]);
}
else
{
hash[sum]=i;
}
}
return ans;
}
};8.矩阵区域和
题目解释：
算法原理：二维前缀和
解法：二维前缀和（显而易见）
我们先回顾一下二维前缀和的步骤
步骤1：预处理出二维前缀和矩阵
步骤2：使用二维前缀和矩阵
回归我们本题，其实问题现在就变成了我们要找到原矩阵每个位置四周扩充k单位时的矩阵范围的左上角和右下角在原矩阵的位置，其实很好找，设该位置下标为i，j的话，左上角位置下标就应该是max(0,i-k)【要防止越过[0] [0]】和max(0,j-k)，而右下角位置下标就应该是min(m-1,i+k)【要防止越过[m-1] [n-1] (m-1为行下标最大值，n-1为列下标最大值)】，y就应该是min(m-1,j+k)
然后要特别注意的是我们在二维前缀和模板那道题中题给矩阵下标和我们的dp数组的下标都是从[1] [1]开始的，而这里的原数组是从[0] [0]开始，所以得进行下标的映射：我们得在dp数组左加一列，右加一行来进行映射（不然在处理边界情况时会很麻烦），这样dp中的（x，y）对应的是mat原矩阵中的（x-1，y-1）->dp[1] [1]对应mat[0] [0]，所以在我们预处理出dp的公式应修改为：dp[i] [j]=dp[i-1] [j]+dp[i] [j-1]-dp[i-1] [j-1]+mat[i-1] [j-1]
我们在使用dp数组时求的左上角和右下角位置时也得都加上1来映射
解题代码：c++
class Solution {
public:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k)
{
//使用二维前缀和算法
//1.预处理出二维前缀和dp数组
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];
}
}
//2.使用前缀和数组
vector<vector<int>> ans(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;
ans[i][j]=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];
}
}
return ans;
}
};