Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.
Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.
Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.
思路：
range sum一般會轉(zhuǎn)化為前綴和的問題prefix sum
解法（分治法）：
int countRangeSum(vector<int>& nums, int lower, int upper)
{
//get the prefix sum
vector<long long> prefix(nums.size() + 1, 0);
for(int i = 1; i<=nums.size(); i++)
prefix[i] = prefix[i-1] + nums[i-1];
return countMergeSort(prefix, 0, nums.size(), lower, upper);
}
int countMergeSort(vector<long long>& prefix, int start, int end, int lower, int upper)
{
if(start >= end) return 0;
int mid = (start + end) >> 1;
int count = countMergeSort(prefix, start, mid, lower, upper) + countMergeSort(prefix, mid+1, end, lower, upper);
vector<long long> tmp(end-start+1);
int lowerBound = mid+1, upperBound = mid+1, right = mid+1, tmpindex = 0;
for(int left = start; left<=mid; left++)
{
while(lowerBound<=end && prefix[lowerBound] - prefix[left] < lower)
lowerBound++;
while(upperBound<=end && prefix[upperBound] - prefix[left] <= upper)
upperBound++;
count += upperBound - lowerBound;
while(right<=end && prefix[right] < prefix[left])
tmp[tmpindex++] = prefix[right++];
tmp[tmpindex++] = prefix[left];
}
for(int i = 0; i<tmpindex; i++)
prefix[start+i] = tmp[i];
return count;
}
伴隨著對prefix sum數(shù)組（不是原數(shù)組）的歸并排序，我們在O(nlogn)時間找到了滿足條件的前綴和之差的個數(shù)。
