算法专题四: 前缀和
1. 前缀和
算法思路:
根据题意, 创建一个前缀和数组, dp[i] = dp[i -1] + arr[i], 再使用前缀和数组, 要求的区域ret = dp[r] - dp[l-1], 这里我们为什么要这样求dp[i]呢? 还要绕一大圈子, 直接相加不就行了 , 但是如果直接相加求还不如我们的暴力解法呢, 这里还要开辟空间, 但是我们使用dp[i]求解只需遍历一遍数组即可求出前缀和
需要注意:
- 创建前缀和数组默认从0开始, 如果我们从1开始访问则需要先将数组初始化好,
- 因为dp[i] 的大小可能超过int所以需要创建long long类型的数组.
编写代码:
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n = 0, q = 0;
cin>>n>>q;
vector<long long> dp(n+1,0);
int num = 0;
for(int i = 1; i <= n; i++)
{
cin>>num;
dp[i] = dp[i-1] + num;
}
while(q--)
{
int l,r;
cin>>l>>r;
cout<<dp[r] - dp[l-1]<<endl;
}
return 0;
}
// 64 位输出请用 printf("%lld")2. 二维前缀和
算法思路:
分析题意, 很显然如果我们使用暴力解法一定会超时的. 首先分析题目, 我们可以先预处理出来一个前缀和矩阵如下图所示, 求出每一个dp[i][j]
然后我们使用dp[i][j],根据所求的区域我们就可以找出一个求出结果的公式, 于是我们就可以搞出来一个时间复杂度为O(N)的算法,当然空间复杂度也为O(N).
编写代码:
#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] - dp[i-1][j-1] + arr[i][j];
}
}
int x1,y1,x2,y2;
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;
}3. 寻找数组的中心下标
算法思路1:
分析题意, 发现可以使用前缀和来解决, 首先预处理出来一个前缀和数组, 然后我们只需在遍历一遍前缀和数组, 只要找到一个位置前面的区域和后面的区域相同, 则就找到了该位置, 但是注意我们的dp是从1开始的所以返回结果需要-1, 如果没有找到返回-1即可, 注意预处理前缀和数组的时候与原数组的映射关系.
编写代码:
class Solution {
public:
int pivotIndex(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n+1,0);
for(int i = 1; i <= n ;i++)
{
dp[i] = dp[i-1] + nums[i-1];
}
for(int i = 1; i <= n ;i++)
{
if(dp[i-1] == (dp[n] - dp[i]))
return i-1;
}
return -1;
}
};算法思路二:
既然我要算左边和右边的和是否相等, 那么我们不妨弄两个的dp数组, 一个前缀和一个后缀和, 对于前缀和我们只需要求出i之前的所有元素之和即可, 对于后缀和我们只需要求出i位置之后的所有元素之和即可, 但是注意细节我们需要考虑第一次计算会访问越界的情况, 所以我们需要提前把f[0]和g[n-1]这个位置处理好,而vector默认就为0.
编写代码:
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] = 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++)
{
if(g[i] == f[i]) return i;
}
return -1;
}
};4. 除自身以外数组的乘积
算法思路:
有了上一题思路二的方法, 对于这道题我们不难解决, 只需求出对于i之前的前缀积以及对于i之后的后缀积即可, 遍历i位置此时answer[i]的位置就是f[i]*g[i], 但是注意细节,对于f[0]和g[n-1]我们要处理成1, 默认第一个位置之前的积为1,最后一个位置也是.
编写代码:
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] = g[i] * f[i];
return ret;
}
};5. 和为k的子数组
算法思路:
首先我们肯定会想到暴力求解, 但是时间复杂度为O(N^2), 那可不可以使用双指针呢, 也就是我们的滑动窗口, 也不可以, 因为会有负数, 并没有单调性.
对于一个数组, 我们要求这个数组中和为k的子数组, 比如遍历到i位置, 我们要求i往前的和为k的子数组, 仅需从0位置查找, 找到和为sum[i] - k的子数组即可, 所以我们的前缀和思想又可以派上用场了.
首先我们先计算出前缀和, 但是我们并不需要创建一个前缀和数组, 仅需把每一次的结果记录到sum即可, 遍历一遍数组, 遍历到i位置就找i位置之前有没有sum = nums[i] - k的, 我们可以把每一次的结果放到哈希表中, 但是注意我们并不需要i这个位置的和, 而是i之前的, 所以我们只保存i之前的前缀和即可, 如果有则ret++,继续下一次查找, 但是注意如果整个数组等于k,也就是遍历到第一个位置我们需要在0到-1这个区间查找, 所以我们需要处理hash[0] = 1.
编写代码:
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int,int> hash;
int sum = 0, ret = 0;
hash[0] = 1;
for(int i = 0; i < nums.size();i++)
{
sum += nums[i];
if(hash.count(sum - k)) ret += hash[sum - k];
hash[sum]++;
}
return ret;
}
};6. 和可被K整除的子数组
算法思路:
本道题依然不能使用滑动窗口来解决, 更上一道题思路类似, 只不过我们这道题哈希表里面存放的是sum的余数, 当遍历到i位置的时候只需要判断在i位置之前和除以k的余数是否等于sum除以k的余数, 因为同余定理, 可以看下图
也就是我们仅需在i位置前找到x%k等于sum%即可, 所以判断的时候我们需要判断sum的余数, 所以哈希表里面我们需要存放余数, 但是C++中余数是由负数的, 负数和正数取余结果不一样, 所以我们需要进行修正. 使用sum遍历数组, 并且求出sum的余数r, 然后先判断sum之前的余数是否等于r, 如果等于则更新ret,最后将这个r也丢入到哈希表中.
编写代码:
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
unordered_map<int,int> hash;
hash[0 % k] = 1;
int sum = 0, ret = 0;
for(int i = 0; i < nums.size() ; i++)
{
sum += nums[i];
int r = (sum % k + k) % k;
if(hash.count(r)) ret += hash[r];
hash[r]++;
}
return ret;
}
};7. 连续数组
算法原理:
这一道题没有单调性, 我们还是不能使用滑动窗口, 先把0修改成-1,我们就可以发现规律, i位置和在[0,i-1]位置的值相等, 即就能找到k数组, 因为正负抵消, 遍历到i位置我们判断该位置之前是否有和正好等于sum, 如果有则我们更新结果, 这里注意我们哈希表中需要存储下标, 因为结果需要我们求出长度, 如果有重复的sum, 我们只保存最早出现的那个下标.
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;
if(hash.count(sum)) ret = max(ret,i - hash[sum]);
else hash[sum] = i;
}
return ret;
}
};8. 矩阵区域和
算法思路:
首先读懂题意, 如下图所示, 也就是answer数组中的每一个位置就是mat当前位置的值向周围拓展k个单位元素的和.接下来进行分析
这道题要求我们求出拓展k个单位的和, 我们应该联想到一个算法, 二维前缀和dp.回忆一下二维前缀和的用法.如果说我们要求一个矩阵的前缀和数组, 则dp[ i ] [ j ] = dp[ i - 1 ] [ j ] + dp[ i ] [ j-1 ] - dp[ i - 1] [j - 1] + arr[ i ] [ j ]
对于使用则有, 如果我们要求某一段区域的和, 则 ret = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]
可以看出, 我们只要想求某段区域的和则前缀和数组中, 仅需知道这块区域的左上角下标个右下角下标即可,本题我们也可以用这样的思路, 但是有几个细节需要注意:
1, 注意我们创建dp数组时, 为了避免越界访问一般下标从1开始, 但是本题所给的数组mat是从下标0 开始, 所以我们它的dp数组需要稍作修改, 当时用到mat时, 将下标+1处理
然后创建我们的ret数组, ret数组中的每一个位置我们都需要使用到dp数组, 所以需要求每一个位置的左上角位置与右下角位置的下标, 以便于正确的使用dp数组.根据下面我们求出该区域与使用dp数组的映射关系, 然后对于每一个位置分别求其结果.
编写代码:
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[x1 - 1][y2] - dp[x2][y1-1] +dp[x1-1][y1-1];
}
}
return ret;
}
};完
腾讯云开发者
