[前缀和+二分法]leetcode327：区间和的个数(hard)

前缀和+二分法]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;}
};