【算法篇】前缀和

用户11029103

发布于 2025-01-15 08:29:32

1660

文章被收录于专栏：技术学习技术学习

1. 一维模版

题目链接：牛客1 题目描述：

#include<iostream>
#include<vector>
using namespace std;

int main() {
    int n,q;
    cin>>n>>q;
    vector<int> v1(n+1);
    vector<long long int> dp(n+1);  
    for(int i=1;i<=n;i++)
    {
        cin>>v1[i];
        dp[i]=dp[i-1]+v1[i];
    }
    int l,r;
    while(q--)
    {
        cin>>l>>r;
        cout<<dp[r]-dp[l-1]<<endl;
    }
    return 0;
}

2. 二维模版

题目链接：牛客2 题目描述：

#include <iostream>
#include<vector>
using namespace std;
int main()
{
    int n,m,q;
    cin>>n>>m>>q;
    vector<vector<int>> v1(n+1,vector<int>(m+1));
    vector<vector<long long int>> dp(n+1,vector<long long int>(m+1));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>v1[i][j];
            dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+v1[i][j];
        }
    }
    int x1,y1,x2,y2;
    while(q--)
    {
      cin>>x1>>y1>>x2>>y2;
      cout<<dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1]<<endl;    
    }

    return 0;
}

3. 除自身以外数组的乘积

题目链接：除自身以外数组的乘积 题目描述：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> dpf(n),dpg(n),result(n);
        dpf[0]=dpg[n-1]=1;
        for(int i=1;i<n;i++)
        {
            dpf[i]=dpf[i-1]*nums[i-1];
        }
        for(int i=n-2;i>=0;i--)
        {
            dpg[i]=dpg[i+1]*nums[i+1];
        }
        for(int i=0;i<n;i++)
        {
            result[i]=dpf[i]*dpg[i];
        }
        return result;
    }
};

4. 和为K的子数组个数

题目链接：和为K的子数组个数 题目描述：

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {

        unordered_map<int,int> hash;
        int sum=0,count=0;
        hash[0]=1;
        for(int i=0;i<nums.size();i++)
        {
            sum+=nums[i];//当前位置前缀和
            if(hash.count(sum-k))
            {
                count+=hash[sum-k];
            }
            hash[sum]++;
        }

        return count;
    }
};

5. 和可被 K 整除的子数组

题目链接：和可被 K 整除的子数组 题目描述：

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int,int> hash;//存前缀和的余数
        hash[0]=1;
        int sum=0,count=0;
        for(int i=0;i<nums.size();i++)
        {
            sum+=nums[i];
            int p1=(sum%k+k)%k;
            if(hash.count(p1))
            {
                count+=hash[p1];
            }
            hash[p1]++;
        }
        return count;
    }
};

nums = [4, 5, 0, -2, -3, 1], k = 5

代码逻辑详解 关键变量的作用

sum: 当前的前缀和。
hash: 一个哈希表，记录前缀和的余数出现的次数。
- hash[0] = 1: 初始设置表示前缀和本身就是
0 \bmod k
的情况。
count: 用来记录满足条件的子数组数量。

初始化：
- hash = {0: 1}
- sum = 0
- count = 0

逐步遍历数组 第 1 步：i = 0, nums[i] = 4

累加前缀和：sum = sum + nums[i] = 0 + 4 = 4
计算余数：p1 = (sum % k + k) % k = (4 % 5 + 5) % 5 = 4
检查哈希表中是否存在余数 p1 = 4：
- 不存在，说明没有子数组可以被 5 整除。
更新哈希表：
- hash[4] = 1
当前状态：
- hash = {0: 1, 4: 1}
- count = 0

第 2 步：i = 1, nums[i] = 5

累加前缀和：sum = sum + nums[i] = 4 + 5 = 9
计算余数：p1 = (sum % k + k) % k = (9 % 5 + 5) % 5 = 4
检查哈希表中是否存在余数 p1 = 4：
- 存在，出现过 1 次。
- 增加计数：count = count + hash[4] = 0 + 1 = 1
更新哈希表：
- hash[4] = 2
当前状态：
- hash = {0: 1, 4: 2}
- count = 1

第 3 步：i = 2, nums[i] = 0

累加前缀和：sum = sum + nums[i] = 9 + 0 = 9
计算余数：p1 = (sum % k + k) % k = (9 % 5 + 5) % 5 = 4
检查哈希表中是否存在余数 p1 = 4：
- 存在，出现过 2 次。
- 增加计数：count = count + hash[4] = 1 + 2 = 3
更新哈希表：
- hash[4] = 3
当前状态：
- hash = {0: 1, 4: 3}
- count = 3

第 4 步：i = 3, nums[i] = -2

累加前缀和：sum = sum + nums[i] = 9 + (-2) = 7
计算余数：p1 = (sum % k + k) % k = (7 % 5 + 5) % 5 = 2
检查哈希表中是否存在余数 p1 = 2：
- 不存在。
更新哈希表：
- hash[2] = 1
当前状态：
- hash = {0: 1, 4: 3, 2: 1}
- count = 3

第 5 步：i = 4, nums[i] = -3

累加前缀和：sum = sum + nums[i] = 7 + (-3) = 4
计算余数：p1 = (sum % k + k) % k = (4 % 5 + 5) % 5 = 4
检查哈希表中是否存在余数 p1 = 4：
- 存在，出现过 3 次。
- 增加计数：count = count + hash[4] = 3 + 3 = 6
更新哈希表：
- hash[4] = 4
当前状态：
- hash = {0: 1, 4: 4, 2: 1}
- count = 6

第 6 步：i = 5, nums[i] = 1

累加前缀和：sum = sum + nums[i] = 4 + 1 = 5
计算余数：p1 = (sum % k + k) % k = (5 % 5 + 5) % 5 = 0
检查哈希表中是否存在余数 p1 = 0：
- 存在，出现过 1 次。
- 增加计数：count = count + hash[0] = 6 + 1 = 7
更新哈希表：
- hash[0] = 2
当前状态：
- hash = {0: 2, 4: 4, 2: 1}
- count = 7

遍历完成后，count = 7，即共有 7 个子数组的和可以被 5 整除。

6. 连续数组

题目链接：连续数组 题目描述：

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        // 将数组中的 0 转换为 -1
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0) nums[i] = -1;
        }
        
        // 使用哈希表记录前缀和首次出现的位置
        unordered_map<int, int> hash;
        hash[0] = -1; // 初始化：前缀和为 0 时的位置是 -1

        int sum = 0;     // 当前前缀和
        int maxLength = 0; // 最长子数组长度

        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];

            // 如果前缀和 sum 已经存在于哈希表中，更新最长长度
            if (hash.count(sum)) {
                maxLength = max(maxLength, i - hash[sum]);
            } else {
                // 如果前缀和 sum 第一次出现，记录其位置
                hash[sum] = i;
            }
        }

        return maxLength;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-01-14，如有侵权请联系 cloudcommunity@tencent.com 删除

hash