本文我们处理一类用数据结构维护前缀和解决的问题基础版本为**[是否存在/存在多少]区间和为 target**。将数组改为矩阵和树得到二维版本和树形版本的问题。以及将“等于”改为“大于”又可以得到一个变种问题本文分别解决这些问题有的问题此前解决过将给出文章链接总结如下问题题目链接维护前缀和的数据结构是否存在区间和为 target-哈希集合有多少区间和为 target560. 和为K的子数组哈希映射有多少矩阵和为 target1074. 元素和为目标值的子矩阵数量哈希映射有多少路径和为 target437. 路径总和 III哈希映射有多少区间和大于 target327. 区间和的个数线段树/树状数组经典一问是否存在区间和为 target给定数组 问 上有没有一个区间其和为 target。算法前缀和 哈希集合对于这经典一问思路如下当扫描到 i 时 的前缀和都已经求过了把它们维护到 unordered_set 中求完当前值 a[i] 对应的前缀和 S[i1], 在插入到 unordered_set 之前先问S[i1] - target 在 unordered_set 中是否出现如果出现则找到答案。基础问题有多少区间的和为 target560. 和为K的子数组给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。提示1 nums.length 2e4-1000 nums[i] 1000-1e7 k 1e7示例 1输入nums [1,1,1], k 2输出2示例 2输入nums [1,2,3], k 3输出2算法前缀和 哈希表在经典一问的基础上把问是否存在该为问存在多少个则得到当前的变种问题。整体思路与经典一问一模一样。仅把 unordered_set 改成 unordered_map 就可以。代码 (C)class Solution {public:int subarraySum(vectorint nums, int k) {// 把所有前缀和保存到 unordered_map 中// 一遍 init 前缀和数组一遍把前缀和存入 map// 遍历的新的前缀和 S[i] 的时候看有 map 没有元素为 S[i] - targetif(nums.empty()) return 0;int n nums.size();vectorint sums(n 1, 0); // sums[0] 0 是第一个前缀和unordered_multisetint sum_count;sum_count.insert(0); // 0 要初始化进去int result 0;for(int i 1; i n 1; i){sums[i] nums[i - 1] sums[i - 1];result sum_count.count(sums[i] - k);sum_count.insert(sums[i]);}return result;}};树形版本有多少路径的和为 target基本问题是问数组上有多少个区间的和为 target。将数组改为树问有多少路径的和为 target即为基本问题的树形版本也就是题目 437. 路径总和 III。算法DFS 前缀和 哈希映射dfs(前序遍历)时栈里存的是当前节点到根的链这条链上的和可以作为前缀和维护在 unordered_map 里。在维护的时候需要注意从左子树跳到右子树的时候左子树的所有节点对应的前缀和要先从 unordered_map 中删掉。参考文章 力扣437-路径总和3。二维版本有多少矩形的和为 target基本问题是问数组上有多少个区间的和为 target。将数组改为矩阵问有多少矩形的和为 target即为基本问题的二维版本也就是题目 1074. 元素和为目标值的子矩阵数量。算法前缀和 哈希映射参考文章 力扣1074-元素和为目标值的子矩阵数量。有多少区间和大于 target327. 区间和的个数给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中值位于范围 [lower, upper] 包含 lower 和 upper之内的 区间和的个数 。区间和 S(i, j) 表示在 nums 中位置从 i 到 j 的元素之和包含 i 和 j (i ≤ j)。示例 1输入nums [-2,5,-1], lower -2, upper 2输出3解释存在三个区间[0,0]、[2,2] 和 [0,2] 对应的区间和分别是-2 、-1 、2 。示例 2输入nums [0], lower 0, upper 0输出1提示1 nums.length 1e5-2^31 nums[i] 2^31 - 1-1e5 lower upper 1e5题目数据保证答案是一个 32 位 的整数算法前缀和 权值树状数组基本问题是问数组上有多少个区间的和为 target。把问题改为问有多少个区间的和大于/小于 target记为当前的变种问题。整体思路与经典一问基本一样只是把 unordered_set 改成权值线段树/权值树状数组树上保存前缀和及其对应的计数值。对于一个前缀和的值 sums[i]我们要找的是 target - sums[i]因此权值线段树/树状数组的横坐标是所有的 target - sums[i]纵坐标是计数。代码 (C)class BIT {public:BIT():sums(1, 0){}BIT(int n):sums(n 1, 0){}void update(int index, int delta){int n sums.size();while(index n){sums[index] delta;index _lowbit(index);}}int query(int i){int sum 0;while(i 0){sum sums[i];i - _lowbit(i);}return sum;}private:vectorint sums;int _lowbit(int x){return x (-x);}};class Solution {public:int countRangeSum(vectorint nums, int lower, int upper) {if(nums.empty()) return 0;int n nums.size();// 前缀和vectorll sums(n 1, 0);for(int i 1; i n; i)sums[i] sums[i - 1] nums[i - 1];// 离散化vectorll x(sums.begin(), sums.end());for(ll sum: sums){x.push_back(sum - (ll)lower);x.push_back(sum - (ll)upper);}sort(x.begin(), x.end());x.erase(unique(x.begin(), x.end()), x.end());int m x.size();BIT bit(m);int result 0;bit.update(_find(0, x), 1);for(int i 0; i n; i){ll cur sums[i 1];result bit.query(_find(cur - (ll)lower, x)) - bit.query(_find(cur - (ll)upper, x) - 1);bit.update(_find(cur, x), 1);}return result;}private:using ll long long;int _find(ll v, const vectorll x){return lower_bound(x.begin(), x.end(), v) - x.begin() 1;}};● 二维的滑动窗口最大值问题● 基于一维问题的解法解决二维问题● 滑动窗口最大值问题