58网站开发要多少钱,开发公司年终总结,惠州网站搭建,推广信息哪个平台好前缀和 文章目录 前缀和一维应用 二维差分一维 二维扩展1、前缀和与哈希表 一维
一个数组prefix中#xff0c;第i个元素表示nums[0]至nums[i-1]的总和#xff0c;那么我们就称这个prefix数组是nums数组的前缀和。 prefix [ i ] ∑ j 0 i nums [ j ] \text{prefix}[i] \s…前缀和 文章目录 前缀和一维应用 二维差分一维 二维扩展1、前缀和与哈希表 一维
一个数组prefix中第i个元素表示nums[0]至nums[i-1]的总和那么我们就称这个prefix数组是nums数组的前缀和。 prefix [ i ] ∑ j 0 i nums [ j ] \text{prefix}[i] \sum_{j0}^{i} \text{nums}[j] prefix[i]j0∑inums[j]
应用
1、快速计算下标为[i , j]区间的和。
prefix[j1]- prefix[i]即为下标[i , j]之间元素的总和。
二维 class NumMatrix {vectorvectorint sum;
public:NumMatrix(vectorvectorint matrix) {int m matrix.size(), n matrix[0].size();sum.resize(m 1, vectorint(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 和r1 位置执行相应操作即可。
二维 扩展
1、前缀和与哈希表
力扣560.和为k的子数组 借助哈希表中判定重复元素的功能可以帮忙判断当前的前缀和-K是否出现在哈希表中如果有那么久数量加一如果没有就将当前前缀和压入哈希表。
class Solution {
public:int subarraySum(vectorint nums, int k) {unordered_mapint, int haxi; // 用于存储前缀和出现次数haxi[0] 1; // 初始化表示前缀和为0出现一次vectorint 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(vectorint nums, int k) {int ans 0, s 0;unordered_mapint, 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
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
