题目来源
给一个数组,求在某个范围内的子串和个数。
这道题搞了半天,理解了半天,写了半天,感觉自己弱爆了。
主要在于利用和数组,利用归并排序,分成两堆的时候,前后是有序的,就是说右堆的元素在左堆的元素和索引的后边,所以可以直接两个和相减表示原数组的某个子串和。
然后归并排序的过程也很巧妙,利用了一个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;
}
};
网友评论