给定一个整数数组 nums，返回区间和在 [lower, upper] 之间的个数，包含 lower 和 upper。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。
说明:
最直观的算法复杂度是 O(n) ，请在此基础上优化你的算法。
示例:

输入: nums = [-2,5,-1], lower = -2, upper = 2,
输出: 3 
解释: 3个区间分别是: [0,0], [2,2], [0,2]，它们表示的和分别为: -2, -1, 2。

哈希表超时

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        unordered_map<long, int> hashMap{{0,1}};
        long sum = 0;
        int res = 0;
        for(int i =0;i<nums.size();i++){
            sum += nums[i];
            for(int j = lower;j<= upper;j++){
                if(hashMap.count(sum - j)){
                    res += hashMap[sum - j];
                }
            }
            hashMap[sum]++;
        }
        return res;
    }
};

Multiset

c++语言中，multiset是库中一个非常有用的类型，它可以看成一个序列，插入一个数，删除一个数都能够在O(logn)的时间内完成，而且他能时刻保证序列中的数是有序的，而且序列中可以存在重复的数。

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        int size = nums.size();
        multiset<long long> preSums;
        long long preSum = 0;
        int res = 0;

        for(int num:nums){
            preSum += num;
            if(preSum >= lower && preSum <= upper){
                res++;
            }
            if(preSums.size() != 0 ){
                long long lower_b = preSum - upper;
                long long upper_b = preSum - lower;
                auto it1 = preSums.lower_bound(lower_b);
                auto it2 = preSums.upper_bound(upper_b);
                res += std::distance(it1, it2);
            }
            preSums.insert(preSum);
        }
        return res;
    }
};

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        multiset<long long> helper;
        helper.insert(0);
        int ans=0;
        long long sum=0;
        for (int &i:nums)
        {
            sum+=i;
            ans+=distance(helper.lower_bound(sum-upper),helper.upper_bound(sum-lower));
            helper.insert(sum);
        }
        return ans;
    }
};