区间和的个数

给你一个整数数组 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;
    }
};