327.区间和的个数

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

思路：归并排序、前缀和数组 

首先，在 merge 函数中做点手脚，当 presum[lo..mid] 和 presum[mid+1..hi] 两个子数组完成排序后，对于 presum[lo..mid] 中的每个元素 presum[i]，去 presum[mid+1..hi] 中寻找符合条件的 presum[j] 就行了。            条件：lower=

实现代码中的start和end类似于在维护一个滑动窗口，窗口中的值均是符合条件的presum[j]，count+=end-start。

class Solution {
public:
    int lo,up;
    int count=0;
    vector<long> tmp;
    int countRangeSum(vector<int>& nums, int lower, int upper) 
    {
        lo=lower;
        up=upper;
        vector<long> presum;
        presum.resize(nums.size()+1);
        tmp.resize(nums.size()+1);
        for(int i=0;isize();i++)
        {
            presum[i+1]=presum[i]+nums[i];
        }
        sort(presum,0,presum.size()-1);
        return count;
    }
    void sort(vector<long>& presum,int low,int high)
    {
        if(low>=high)
        return ;
        int mid=low+(high-low)/2;
        sort(presum,low,mid);
        sort(presum,mid+1,high);
        merge(presum,low,mid,high);
    }
    void merge(vector<long>& presum,int low,int mid,int high)
    {
        for(int i=low;i<=high;i++)
        {
            tmp[i]=presum[i];
        }
        int start=mid+1,end=mid+1;
        for(int i=low;i<=mid;i++)
        {
            while(start<=high&&presum[start]-presum[i]
            {
                start++;
            }
            while(end<=high&&presum[end]-presum[i]<=up)
            {
                end++;
            }
            count+=end-start;
        }
        int left=low,right=mid+1;
        for(int i=low;i<=high;i++)
        {
            if(left==mid+1)
            {
                presum[i]=tmp[right++];
            }
            else if(right==high+1)
            {
                presum[i]=tmp[left++];
            }
            else if(tmp[left]
            {
                presum[i]=tmp[left++];
            }
            else
            {
                presum[i]=tmp[right++];
            }
        }
    }
};