前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >算法专题四: 前缀和

算法专题四: 前缀和

作者头像
用户11317877
发布2024-10-16 14:42:21
550
发布2024-10-16 14:42:21
举报
文章被收录于专栏:学习

1. 前缀和

算法思路:

根据题意, 创建一个前缀和数组, dp[i] = dp[i -1] + arr[i], 再使用前缀和数组, 要求的区域ret = dp[r] - dp[l-1], 这里我们为什么要这样求dp[i]呢? 还要绕一大圈子, 直接相加不就行了 , 但是如果直接相加求还不如我们的暴力解法呢, 这里还要开辟空间, 但是我们使用dp[i]求解只需遍历一遍数组即可求出前缀和

需要注意:

  1. 创建前缀和数组默认从0开始, 如果我们从1开始访问则需要先将数组初始化好,
  2. 因为dp[i] 的大小可能超过int所以需要创建long long类型的数组.

编写代码:

代码语言:javascript
复制
#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).

编写代码:

代码语言:javascript
复制
#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即可, 注意预处理前缀和数组的时候与原数组的映射关系.

编写代码:

代码语言:javascript
复制
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.

编写代码:

代码语言:javascript
复制
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,最后一个位置也是.

编写代码:

代码语言:javascript
复制
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.

编写代码:

代码语言:javascript
复制
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也丢入到哈希表中.

编写代码:

代码语言:javascript
复制
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, 我们只保存最早出现的那个下标.

代码语言:javascript
复制
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数组的映射关系, 然后对于每一个位置分别求其结果.

编写代码:

代码语言:javascript
复制
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;
    }
};

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-10-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 前缀和
  • 2. 二维前缀和
  • 3. 寻找数组的中心下标
  • 4. 除自身以外数组的乘积
  • 5. 和为k的子数组
  • 6. 和可被K整除的子数组
  • 7. 连续数组
  • 8. 矩阵区域和
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档