題目來源
給一個數(shù)組蕊程，求在某個范圍內(nèi)的子串和個數(shù)。
這道題搞了半天辨赐，理解了半天惭婿，寫了半天换吧，感覺自己弱爆了。
主要在于利用和數(shù)組贯莺，利用歸并排序，分成兩堆的時候撕蔼，前后是有序的，就是說右堆的元素在左堆的元素和索引的后邊讼溺，所以可以直接兩個和相減表示原數(shù)組的某個子串和。
然后歸并排序的過程也很巧妙视译，利用了一個cache來存儲排好序的數(shù)組汪茧。
左堆和右堆元素比較，因為左右堆都是各自排好序的别威，所以其實本質(zhì)上就是雙指針向后移動丧失。
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;
}
};
