题目来源
给一个数组，求在某个范围内的子串和个数。
这道题搞了半天，理解了半天，写了半天，感觉自己弱爆了。
主要在于利用和数组，利用归并排序，分成两堆的时候，前后是有序的，就是说右堆的元素在左堆的元素和索引的后边，所以可以直接两个和相减表示原数组的某个子串和。
然后归并排序的过程也很巧妙，利用了一个cache来存储排好序的数组。
左堆和右堆元素比较，因为左右堆都是各自排好序的，所以其实本质上就是双指针向后移动。
class Solution {
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
int n = nums.size();
if (n == 0)
return 0;
vector<long long> sums(n+1, 0);
for (int i=0; i<n; i++)
sums[i+1] = sums[i] + nums[i];
return mergeSortWhileCount(sums, 0, n+1, lower, upper);
}
int mergeSortWhileCount(vector<long long>& sums, int start, int end, int lower, int upper)
{
if (end - start <= 1)
return 0;
int mid = (start + end) / 2;
int cnt = mergeSortWhileCount(sums, start, mid, lower, upper)
+ mergeSortWhileCount(sums, mid, end, lower, upper);
int j = mid, k = mid, t = mid, len = 0;
vector<long long> cache(end-start, 0);
for (int i=start, s=0; i<mid; i++, s++) {
while (j < end && sums[j] - sums[i] < lower) j++;
while (k < end && sums[k] - sums[i] <= upper) k++;
while (t < end && sums[t] < sums[i]) cache[s++] = sums[t++];
cache[s] = sums[i];
len = s;
cnt += k - j;
}
for (int i=0; i<=len; i++)
sums[start+i] = cache[i];
return cnt;
}
};
