My code:
public class Solution {
public int countRangeSum(int[] nums, int lower, int upper) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
long[] sums = new long[len + 1];
for (int i = 1; i < sums.length; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
return mergesort(sums, 0, len, lower, upper);
}
private int mergesort(long[] sums, int start, int end, int lower, int upper) {
if (start >= end) {
return 0;
}
int mid = start + (end - start) / 2;
int cnt = mergesort(sums, start, mid, lower, upper) + mergesort(sums, mid + 1, end, lower, upper);
long[] cache = new long[end - start + 1];
int k = mid + 1;
int j = mid + 1;
int r = mid + 1;
int t = 0;
for (int i = start; i <= mid; i++) {
while (k <= end && sums[k] - sums[i] < lower) {
k++;
}
while (j <= end && sums[j] - sums[i] <= upper) {
j++;
}
while (r <= end && sums[r] <= sums[i]) {
cache[t] = sums[r];
t++;
r++;
}
cache[t] = sums[i];
t++;
cnt += j - k;
}
while (r <= end) {
cache[t] = sums[r];
t++;
r++;
}
for (int i = start; i <= end; i++) {
sums[i] = cache[i - start];
}
return cnt;
}
}
reference:
https://discuss.leetcode.com/topic/33738/share-my-solution/2
這道題目真的挺難的咐低。我是在做了 count of number smaller after self 之后看這個(gè)解釋，才有了思路见擦。
首先就是一個(gè)累加和 sums, 這個(gè)都能理解。
然后開(kāi)始merge sort
假設(shè)我們已經(jīng)有了left and right part
left is sorted
right is sorted, too
left[start, mid], right[mid + 1, end]
我們需要找的是
i = start
k = mid + 1
j = mid + 1
sums[k] - sums[i] >= lower
sums[j] - sums[i] > upper
then
count += j - k
這是第一步
第二步鲤屡，我們需要merge原數(shù)組
int[] cache = new int[end - start + 1];
int t = 0;
int r = mid + 1;
if (sums[r] <= sums[i]) {
cache[t++] = sums[r++];
}
cache[t] = sums[i];
t++;
最后的最后，千萬(wàn)記得卢未，當(dāng) i > mid 結(jié)束循環(huán)時(shí)堰汉，
不代表 r 已經(jīng) > end 了辽社，也就是說(shuō)翘鸭，merge可能并沒(méi)有結(jié)束。
我們需要繼續(xù)拷貝給 cache[]
題目真的就乓，注意點(diǎn)太多了，太瑣碎了噩翠。有時(shí)間再背一下把。
Anyway, Good luck, Richardo! -- 10/09/2016
