【算法篇】前缀和

Alt

🔥个人主页：Quitecoder

🔥专栏：算法笔记仓

Alt

前缀和是一种常用于处理数组区间求和问题的技巧。它可以用来减少重复计算，使得多次查询区间和的时间复杂度从 O(n) 降低到 O(1)

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: 初始设置表示前缀和本身就是 $\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 转换为 -1for (int i = 0; i < nums.size(); i++) {if (nums[i] == 0) nums[i] = -1;}// 使用哈希表记录前缀和首次出现的位置unordered_map<int, int> hash;hash[0] = -1; // 初始化：前缀和为 0 时的位置是 -1int 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;}
};