前缀和+二分法]leetcode327:区间和的个数(hard)"/>
[前缀和+二分法]leetcode327:区间和的个数(hard)
题目:
题解:
- 前缀和+二分法
- 注意这里使用暴力法的话,会超时的,所以我们需要改进算法。
- 我们使用
multiset
的数据结构来存放前缀和,这样做的好处是自动对元素进行排序,便于二分查找。- 用prefix[i]表示[0,i]的前缀和,然后需要想办法找到区间[0,i]之间还有多少个区间和满足[lower,upper]的范围呢?
- 假如
[j,i]
的区间和满足[lower,upper]的范围,那么lower <= prifix[i]-prifix[j] <= upper
等价于prefix[i]-upper <= prefix[j] <= prefix[i]-lower
,所以现在我们只需要找到有多少个这样的j满足条件就好了。- 我们用
upper_bound
和lower_bound
来找临界值。lower_bound 是找数组中第一个不小于给定值的数(包括等于情况),而 upper_bound 是找数组中第一个大于给定值的数,那么两者相减,就是j的个数。
代码如下:
class Solution {
public://题解:前缀和+二分法//prefix[i]表示[0,i]的前缀和int countRangeSum(vector<int>& nums, int lower, int upper) {int count=0,n=nums.size();multiset<long long> prefix;//存放前缀和,并自动排序prefix.insert(0);long long sum=0;//[j,i]表示区间和,而i是需要判断区间的右端点//lower <= prifix[i]-prifix[j] <= upper 等价于 prefix[i]-upper <= prefix[j] <= prefix[i]-lower//而这里的prefix[i]就对应下面代码中的sum,我们只需要找到有多少个j满足上面的不等式就好了//用multiset的好处是自动排序,这样有利于我们使用二分查找for(int i=0;i<n;++i){sum+=(long long)nums[i];count+=distance(prefix.lower_bound(sum-upper),prefix.upper_bound(sum-lower));prefix.insert(sum);}return count;}
};
更多推荐
[前缀和+二分法]leetcode327:区间和的个数(hard)
发布评论