给你一个整数数组 nums 以及两个整数 lower 和 upper
求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数
一. 前缀和+双重循环（超时）
class Solution {
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
int n = nums.size();
vector<long long> presum(n+1);
for(int i=0;i<n;i++)
presum[i+1] = presum[i] + nums[i];
int count = 0;//区间计数
for(int i=0;i<n;i++){//区间起点
if(nums[i]>=lower&&nums[i]<=upper) count++;//单个数区间
for(int j=i+1;j<n;j++){//区间终点
long long cursum = presum[j+1]-presum[i];
if(cursum>=lower&&cursum<=upper) count++;
}
}
return count;
}
};
二. 前缀和+归并排序+双指针
对于有序的两子区间，可以用前缀和和双指针快速计算满足条件的个数
class Solution {
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
int n = nums.size();
if(n==0) return 0;
vector<long> presum(n+1);
for(int i=0;i<n;i++)//计算前缀和
presum[i+1] = presum[i] + nums[i];
//后面只用看前缀和
return countRange(presum,0,n,lower,upper);
}
int countRange(vector<long>&presum,int l,int r,int lower,int upper){
if(l==r) return 0;//边界条件
int mid = (l+r)/2;
//分治归并
return countRange(presum,l,mid,lower,upper)+
countRange(presum,mid+1,r,lower,upper)+
merge(presum,l,mid,r,lower,upper);
}
int merge(vector<long>&presum,int l,int m,int r,int lower,int upper){
//对于两有序相邻子区间，计算下标对数量，有序是为了方便指针移动，减少查询
int count = 0;
int i = l;//i在左区间初始指针
int lp = m + 1;//右区间初始指针1
int rp = m + 1;//右区间初始指针2
while (i <= m) {//遍历左区间
//找右区间满足条件的值，双指针
while (lp <= r && presum[lp] - presum[i] < lower) lp++;//左闭
while (rp <= r && presum[rp] - presum[i] <= upper) rp++;//右开
count += (rp - lp);
i++;
}
//合并有序数组
int p1 = l; int p2=m+1; //合并区间辅助指针
i=0;//辅助数组初始指针
vector<long> sorted(r-l+1);//合并区间长度
while(p1<=m&&p2<=r)
sorted[i++] = presum[p1]<presum[p2]?presum[p1++]:presum[p2++];
while(p1<=m) sorted[i++] = presum[p1++];
while(p2<=r) sorted[i++] = presum[p2++];
for(i=0;i<sorted.size();i++)
presum[l+i] = sorted[i];
return count;
}
};