給定一個整數(shù)數(shù)組 nums镜盯，返回區(qū)間和在 [lower, upper] 之間的個數(shù)，包含 lower 和 upper毛甲。
區(qū)間和 S(i, j) 表示在 nums 中宛畦，位置從 i 到 j 的元素之和，包含 i 和 j (i ≤ j)猫十。
說明:
最直觀的算法復雜度是 O(n2) 览濒，請在此基礎上優(yōu)化你的算法呆盖。
示例:
輸入: nums = [-2,5,-1], lower = -2, upper = 2,
輸出: 3
解釋: 3個區(qū)間分別是: [0,0], [2,2], [0,2]，它們表示的和分別為: -2, -1, 2贷笛。
代碼
class Solution {
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
int res = 0;
long long sum = 0;
multiset<long long> sums;
sums.insert(0);
for (int i = 0; i < nums.size(); ++i) {
sum += nums[i];
res += distance(sums.lower_bound(sum - upper), sums.upper_bound(sum - lower));
sums.insert(sum);
}
return res;
}
};
