算法笔记（三）——前缀和算法

算法笔记（三）——前缀和算法

前缀和算法是一种用空间换时间的算法，他常常用于解决某些题目或者作为某些高级算法的组成部分

一维前缀和

题目链接：DP34 【模板】前缀和

思路

• 通过数组arr存储输入的 n 个整数，数组 dp存储数组 arr的前缀和
• 使用循环读取数组元素，并计算前缀和 dp
• 进行q 次查询，每次查询给定一个区间[l, r]。查询结果为dp[r] - dp[l-1]，表示数组在区间 [l, r] 的和

C++代码

#include<iostream>
using namespace std;int main()
{int n, q;cin >> n >> q;long long arr[100001]={0}, dp[100001]={0};for(int i = 1; i <= n;++i){cin >> arr[i];dp[i] = arr[i] + dp[i-1];}while(q--){int l, r;cin >> l >> r;cout << dp[r] - dp[l-1] << endl;}return 0;
}

二维前缀和

题目：DP35 【模板】二维前缀和

思路
初始化前缀和

• 构造前缀和数组dp[i][j]，其含义是从(1,1)到(i,j)区域的面积；
• D区域也是dp[i][j]存储的值，其面积也等于 A+B+C+D
• 初始化前缀和dp[i][j] = (A+B)+(A+C)+D - A = dp[i-1][j]+dp[i][j-1]+arr[i][j]-dp[i-1][j-1]

使用前缀和计算

• D = A+B+C+D-(A+B)-(A+C)+A
• D = dp[i][j]-dp[i][j-1]-dp[i-1][j]+dp[i-1][j-1]

C++代码

#include <iostream>
using namespace std;int arr[1100][1100];
long long dp[1100][1100];
int n, m, q, x1, x2, y1, y2;int main() 
{cin >> n >> m >> q;for(int i = 1; i <=n; i++){for(int j = 1; j <= m; j++){cin >> arr[i][j];dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1]; }}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;
}

寻找数组的中心下标

题目：寻找数组的中心下标

思路

• 初始化f表示前缀和，g表示后缀和
• f[i]表示[0,i-1]所有元素的和，
• f[i] = f[i-1] + nums[i-1]；
• g[i]表示[i+1,n-1]所有元素的和，
• g[i] = g[i+1] + nums[i+1];
• 遍历数组nums，找到一个索引，使得 f[i]（左侧元素的和）等于 l[i]（右侧元素的和）

C++代码

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 (f[i] == g[i])return i;return -1;}
};

除自身以外数组的乘积

题目：除自身以外数组的乘积

思路

• 初始化f表示前缀积，g表示后缀积
• f[i]表示[0,i-1]所有元素的积，
• f[i] = f[i - 1] * nums[i - 1]；
• g[i]表示[i+1,n-1]所有元素的积，
• g[i] = g[i+1] * nums[i+1];
• 遍历数组nums，计算res[i]的值

C++代码

class Solution 
{
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> f(n + 1);vector<int> g(n + 1);vector<int> res(n);f[0] = 1,  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++)res[i] = f[i] * g[i];return res;  }
};

和为 K 的子数组

题目：和为 K 的子数组

思路
将问题转化为寻找和为k的子数组，
而不是直接在数组中寻找和为k的连续元素，
这样就可以使问题在一次遍历中解决
具体来说就是：对于每个前缀和，都检查是否存在一个早先的前缀和，使得它们的差等于k。如果存在，就找到了一个和为k的子数组

• 初始化一个哈希表 hash，其中hash[0]表示和为 0 的子数组的个数，初始化为 1
• 两个变量 sum和 ret，其中 sum 表示当前累积的和，ret 表示满足条件的子数组的个数
• 遍历数组 nums，累积和并更新哈希表
  对于每个元素 x，更新 sum += x
  检查是否存在之前的累积和 sum - k 在哈希表中，如果存在，则累加 hash[sum - k] 到 ret。更新哈希表中的当前累积和sum 的计数

C++代码

class Solution 
{
public:int subarraySum(vector<int>& nums, int k) {// K：前缀和// V：前缀和出现的次数unordered_map<int, int> hash;int sum = 0, ans = 0;// 初始化时为空区间，则前缀和为0，出现的次数为1hash[0] = 1;for(int num : nums) {sum += num; ans += hash[sum - k]; // 要么为0，要么为sum - k出现的次数hash[sum]++;}return ans;}
};

和可被 K 整除的子数组

题目：和可被 K 整除的子数组

补充

1. 同余定理
   若(a-b) % p = k......0，则a % p = b % p
2. C++、Java中 负数%正数等于负数
   修正 a % p + p
   为了a>0或a<0统一后(a % p + p) % p

思路
和上题基本相同，转化为在[0, i - 1]中，找到有多少个前缀和的余数等于(sum % k + k) % k

• 在 for(auto x : nums) 的循环中，遍历数组nums。对于每个元素x
• sum += x; 累加当前位置的元素，得到当前位置的前缀和。
• int r = (sum % k + k) % k
• if(hash.count(r)) ret += hash[r]; 检查之前是否存在相同的余数r，如果存在，则将哈希表中对应的次数累加到结果 ret 中。
• hash[r]++; 更新哈希表，将当前余数 r 的次数加一

C++代码

class Solution 
{
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int, int> hash;hash[0] = 1; // 初始时，前缀和为 0 的余数的个数为 1 int sum = 0;int ret = 0;for(auto x : nums){sum += x; // 当前位置前缀和int r = (sum % k + k) % k;if(hash.count(r)) // 检查之前是否存在相同的余数 r，如果存在ret += hash[r]; hash[r]++; // 更新哈希表，将当前余数 r 的次数加一}return ret;}
};

连续数组

题目：连续数组

思路

• 将 0 看作 -1，问题就转换成在数组中，找出最长的子数组使其和为0
• unordered_map<int, int> hash表示创建一个哈希表，用于存储前缀和以及对应的出现位置
• 遍历数组nums对于每个元素 nums[i]，如果 nums[i] 是 0，则令 sum += -1；如果是1，则令 sum += 1。这样sum就表示当前位置的前缀和；
• 判断哈希表中是否存在当前前缀和sum。如果存在，说明从上次该前缀和出现的位置到当前位置的子数组的和为零，更新最长长度 ret。
• 如果哈希表中不存在当前前缀和sum，则将当前前缀和和对应的位置存入哈希表中

C++代码

class Solution 
{
public:int findMaxLength(vector<int>& nums) {unordered_map<int,int> hash;hash[0] = -1;int ret = 0;int sum = 0;for(int i = 0; i < nums.size(); ++i){sum += (nums[i] == 1 ? 1 : -1);if(hash.count(sum)) ret = max(ret, i - hash[sum]);else hash[sum]=i;}return ret;}
};

矩阵区域和

题目：矩阵区域和

思路
二维前缀和问题，但是需要处理好边界问题

• int m=mat.size(), n=mat[0].size()获取矩阵的行数和列数
• vector<vector<int>> dp(m+1,vector<int>(n+1))创建二维前缀和数组dp
• dp[i][j]表示矩阵左上角 (0,0)到 (i-1,j-1)的元素和，计算前缀和数组 dp
• 对于每个位置(i,j)，计算块的左上角和右下角的坐标，确保不超过矩阵边界

C++代码

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] + mat[i - 1][j - 1] - dp[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;}
};