当前位置：首页 > news >正文

【杂乱算法】前缀和与差分

news 来源：原创 2024/9/19 22:02:18

前缀和

文章目录

前缀和
- 一维
- - 应用
- 二维
- 差分
- - 一维
- 二维
- 扩展
- - 1、前缀和与哈希表

一维

一个数组prefix中，第i个元素表示nums[0]至nums[i-1]的总和，那么我们就称这个prefix数组是nums数组的前缀和。
$\text{prefix}[i] = \sum_{j=0}^{i} \text{nums}[j]$

应用

1、快速计算下标为[i , j]区间的和。

prefix[j+1]- prefix[i]即为下标[i , j]之间元素的总和。

二维

class NumMatrix {vector<vector<int>> sum;
public:NumMatrix(vector<vector<int>> &matrix) {int m = matrix.size(), n = matrix[0].size();sum.resize(m + 1, vector<int>(n + 1));for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + matrix[i][j];}}}// 返回左上角在 (r1,c1) 右下角在 (r2,c2) 的子矩阵元素和int sumRegion(int r1, int c1, int r2, int c2) {return sum[r2 + 1][c2 + 1] - sum[r2 + 1][c1] - sum[r1][c2 + 1] + sum[r1][c1];}
};作者：灵茶山艾府
链接：https://leetcode.cn/problems/range-sum-query-2d-immutable/solutions/2667331/tu-jie-yi-zhang-tu-miao-dong-er-wei-qian-84qp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

差分

一维

所谓“差分”，是指原数组中每个元素与前一元素之差所形成的数组。
我们知道，对原数组进行诸位累加（前缀计算操作），所得到的数组为前缀和数组。差分数组，则是对其执行前缀计算后，能够得到原数组的那个数组。

差分数组的主要作用，是帮助快速修改某段区间。

因此，当我们想要对原数组的 [l,r] 进行整体修改时，只需要对差分数组的l 和r+1 位置执行相应操作即可。

二维

扩展

1、前缀和与哈希表

力扣560.和为k的子数组
借助哈希表中判定重复元素的功能，可以帮忙判断（当前的前缀和-K）是否出现在哈希表中，如果有那么久数量加一，如果没有就将当前前缀和压入哈希表。

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int, int> haxi; // 用于存储前缀和出现次数haxi[0] = 1; // 初始化，表示前缀和为0出现一次vector<int> qian(nums.size() + 1, 0); // 前缀和数组int ans = 0;// 计算前缀和for (int i = 1; i <= nums.size(); i++) {qian[i] = nums[i - 1] + qian[i - 1];}// 查找满足条件的子数组for (int i = 1; i <= nums.size(); i++) {int complement = qian[i] - k;if (haxi.find(complement) != haxi.end()) {ans += haxi[complement]; // 增加满足条件的子数组个数}haxi[qian[i]]++; // 更新当前前缀和的出现次数}return ans;}
};

或者也可以一次遍历即可。在遍历的同时判断（当前的前缀和-K）是否出现在哈希表中。

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int ans = 0, s = 0;unordered_map<int, int> cnt{{0, 1}}; // s[0]=0 单独统计for (int x : nums) {s += x;// 注意不要直接 += cnt[s-k]，如果 s-k 不存在，会插入 s-kans += cnt.contains(s - k) ? cnt[s - k] : 0;cnt[s]++;}return ans;}
};作者：灵茶山艾府
链接：https://leetcode.cn/problems/subarray-sum-equals-k/solutions/2781031/qian-zhui-he-ha-xi-biao-cong-liang-ci-bi-4mwr/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。