前缀和:
前缀和(Prefix Sum)是一种常用的算法技巧,用于快速计算数组中某一范围的元素之和。
具体来说,前缀和是通过一个新的数组 prefix_sum 来表示原数组每个位置之前(包括当前位置)的所有元素之和。
- 这样可以将查询区间和的时间复杂度从 O(n) 降低到 O(1)。
下面两个关于前缀和的模板题
【模板】前缀和
#include <iostream>
using namespace std;
// 定义常量 N 来表示数组的大小
const int N = 1000001;
// 声明两个数组:'arr' 用来存储输入的值,'dp' 用来存储前缀和
long long arr[N], dp[N];
int main()
{
int n = 0, q = 0;
// 读取数组的元素个数(n)和查询的数量(q)
cin >> n >> q;
// 读取数组元素到 'arr' 中
for(int i = 1; i <= n; i++) cin >> arr[i];
// 计算前缀和并存储在 'dp' 中
// dp[i] 存储从 arr[1] 到 arr[i] 的和
for(int i = 1; i <= n; i++) dp[i] = dp[i - 1] + arr[i];
// 处理每个查询
while(q--)
{
int l = 0, r = 0;
// 读取当前查询的区间 [l, r]
cin >> l >> r;
// 输出从 arr[l] 到 arr[r] 的和,使用前缀和数组
// dp[r] 给出的是从 arr[1] 到 arr[r] 的和,dp[l-1] 给出的是从 arr[1] 到 arr[l-1] 的和,
// 因此 dp[r] - dp[l-1] 就是从 arr[l] 到 arr[r] 的和
cout << dp[r] - dp[l - 1] << endl;
}
return 0;
}
【模板】二维前缀和
#include <iostream>
using namespace std;
// 定义常量 N 来表示二维数组的大小
const int N = 1010;
// 声明二维数组 'arr' 用来存储输入的矩阵元素,'dp' 用来存储前缀和
long long arr[N][N], dp[N][N];
int main()
{
int n = 0, m = 0, q = 0;
// 读取矩阵的行数(n)、列数(m)和查询的数量(q)
cin >> n >> m >> q;
// 读取矩阵元素到 'arr' 中
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> arr[i][j];
}
}
// 计算前缀和并存储在 'dp' 中
// dp[i][j] 存储从 (1,1) 到 (i,j) 的矩阵和
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];
}
}
// 处理每个查询
while(q--)
{
int x1, y1, x2, y2;
// 读取当前查询的矩阵区域 (x1, y1) 到 (x2, y2)
cin >> x1 >> y1 >> x2 >> y2;
// 计算并输出 (x1, y1) 到 (x2, y2) 区域的矩阵和
// 利用前缀和数组 'dp' 计算矩阵区域的和
// dp[x2][y2] 给出从 (1, 1) 到 (x2, y2) 的和,
// dp[x1 - 1][y2] 给出从 (1, 1) 到 (x1-1, y2) 的和,
// dp[x2][y1 - 1] 给出从 (1, 1) 到 (x2, y1-1) 的和,
// dp[x1 - 1][y1 - 1] 给出从 (1, 1) 到 (x1-1, y1-1) 的和,
// 通过这些前缀和,我们能够快速计算出 (x1, y1) 到 (x2, y2) 区域的和。
cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
}
return 0;
}
通过上面两道模板题,我们可以总结出关于一维、以及二维关于前缀和的核心代码
一维:dp[i] = dp[i - 1] + arr[i]
二维:dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j]
寻找数组的中心下标
思路:
该题目与前缀和算法有很大的关系,因为其核心思想是通过前缀和来快速计算一个区间的和。
前缀和算法通常用于解决以下类型的问题:
- 计算数组某一子区间的和。
- 处理多个关于数组区间的查询问题。
class Solution
{
public:
int pivotIndex(vector<int>& nums)
{
// 获取数组的大小
int n = nums.size();
// 创建两个辅助数组,dp1 和 dp2,用来存储前缀和与后缀和
vector<int> dp1(n); // dp1[i] 存储 nums[0] 到 nums[i-1] 的和
vector<int> dp2(n); // dp2[i] 存储 nums[i+1] 到 nums[n-1] 的和
// 计算 dp1 数组,dp1[i] 表示 nums[0] 到 nums[i-1] 的和
for(int i = 1; i < n; i++)
dp1[i] = dp1[i - 1] + nums[i - 1];
// 计算 dp2 数组,dp2[i] 表示 nums[i+1] 到 nums[n-1] 的和
for(int i = n - 2; i >= 0; i--)
dp2[i] = dp2[i + 1] + nums[i + 1];
// 遍历数组,查找满足 dp1[i] == dp2[i] 的索引 i
for(int i = 0; i < n; i++)
{
if(dp1[i] == dp2[i])
return i; // 如果找到匹配的索引,返回该索引
}
// 如果没有找到,返回 -1
return -1;
}
};
该问题的关键在于通过 前缀和 和 后缀和 两个数组,分别计算数组每个元素左边和右边的和,然后判断哪个位置的左右和相等,来找出枢轴索引。利用前缀和的思想将原本需要 O(n^2) 的区间求和操作优化到 O(n),从而提升了程序的效率。
除自身以外的数组的乘积
class Solution
{
public:
vector<int> productExceptSelf(vector<int>& nums)
{
// 获取数组的大小
int n = nums.size();
// 初始化两个辅助数组 dp1 和 dp2,分别用来存储左边的乘积和右边的乘积
// dp1[i] 存储 nums[0] 到 nums[i-1] 的所有元素的乘积
// dp2[i] 存储 nums[i+1] 到 nums[n-1] 的所有元素的乘积
vector<int> dp1(n, 1); // dp1 初始化为 1
vector<int> dp2(n, 1); // dp2 初始化为 1
// 计算 dp1 数组,dp1[i] 存储 nums[0] 到 nums[i-1] 的乘积
for(int i = 1; i < n; i++)
dp1[i] = dp1[i - 1] * nums[i - 1];
// 计算 dp2 数组,dp2[i] 存储 nums[i+1] 到 nums[n-1] 的乘积
for(int i = n - 2; i >= 0; i--)
dp2[i] = dp2[i + 1] * nums[i + 1];
// 初始化返回结果数组 ret
vector<int> ret(n);
// 计算最终结果,ret[i] 是 nums[0] 到 nums[i-1] 的乘积与 nums[i+1] 到 nums[n-1] 的乘积的乘积
for(int i = 0; i < n; i++)
ret[i] = dp2[i] * dp1[i];
return ret; // 返回结果数组
}
};
和为K的子数组
class Solution
{
public:
int subarraySum(vector<int>& nums, int k)
{
// 使用哈希表记录前缀和出现的次数
unordered_map<int, int> hash;
// 初始化哈希表,前缀和为 0 出现 1 次(表示空数组的和为 0)
hash[0] = 1;
// 初始化变量 sum 来记录当前的前缀和,ret 来记录符合条件的子数组个数
int sum = 0, ret = 0;
// 遍历数组 nums,计算前缀和
for(auto x : nums)
{
// 更新当前的前缀和
sum += x;
// 如果哈希表中存在 (sum - k),说明当前前缀和与某个之前的前缀和之间的和为 k
// 也就是说,找到了一个符合条件的子数组
if(hash.count(sum - k))
ret += hash[sum - k];
// 更新哈希表,将当前前缀和 sum 的出现次数加 1
hash[sum]++;
}
// 返回符合条件的子数组个数
return ret;
}
};
和可被K整除的数组
class Solution
{
public:
int subarraysDivByK(vector<int>& nums, int k)
{
// 使用哈希表记录每个前缀和的余数出现的次数
unordered_map<int, int> hash;
// 初始化哈希表,前缀和的余数为 0 出现 1 次(表示空数组的和为 0)
hash[0] = 1;
// 初始化变量 sum 来记录当前的前缀和,ret 来记录符合条件的子数组个数
int sum = 0, ret = 0;
// 遍历数组 nums,计算前缀和
for(auto x : nums)
{
// 更新当前的前缀和
sum += x;
// 计算当前前缀和的余数
// (sum % k + k) % k 确保余数为非负数
int r = (sum % k + k) % k;
// 如果哈希表中存在余数 r,说明存在符合条件的子数组
if(hash.count(r))
ret += hash[r];
// 更新哈希表,将当前余数 r 的出现次数加 1
hash[r]++;
}
// 返回符合条件的子数组个数
return ret;
}
};
连续数组
class Solution
{
public:
int findMaxLength(vector<int>& nums)
{
// 获取数组的大小
int n = nums.size();
// 哈希表用来存储前缀和出现的位置
unordered_map<int,int> hash;
// 初始化哈希表,前缀和为 0 的时候,位置为 -1
hash[0] = -1;
// sum 用来记录当前的前缀和,ret 用来记录最长的子数组长度
int sum = 0, ret = 0;
// 遍历数组 nums,计算每个位置的前缀和
for(int i = 0; i < n; i++)
{
// 如果当前元素是 0,减 1;如果是 1,加 1
sum += nums[i] == 0 ? -1 : 1;
// 如果当前前缀和之前已经出现过,说明存在符合条件的子数组
// 通过 i - hash[sum] 计算当前符合条件的子数组的长度
if(hash.count(sum))
ret = max(ret, i - hash[sum]);
else
// 如果前缀和没有出现过,则将当前前缀和和它的位置加入哈希表
hash[sum] = i;
}
// 返回最长的子数组长度
return ret;
}
};
矩阵区域和
class Solution
{
public:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k)
{
// 获取矩阵的行数和列数
int m = mat.size(), n = mat[0].size();
// 创建一个 dp 数组,用来存储前缀和
// dp[i][j] 表示从 (0, 0) 到 (i-1, j-1) 的矩阵区域的和
vector<vector<int>> dp(m + 1, vector<int> (n + 1));
// 计算前缀和数组 dp
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];
}
}
// 初始化返回结果数组 ret,存储每个位置的子矩阵和
vector<vector<int>> ret(m, vector<int> (n));
// 遍历矩阵,计算每个位置的以 (i, j) 为中心,边长为 2k+1 的子矩阵和
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;
// 利用前缀和计算当前 (i, j) 位置的子矩阵和
ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
}
}
// 返回结果矩阵
return ret;
}
};