327. Count of Range Sum

Description

Given an integer arraynums, return the number of range sums that lie in[lower, upper]inclusive.
Range sumS(i, j)is defined as the sum of the elements innumsbetween indicesiandj(i≤j), inclusive.

Note:
A naive algorithm ofO(n2) is trivial. You MUST do better than that.

Example:
Givennums=[-2, 5, -1],lower=-2,upper=2,
Return3.
The three ranges are :[0, 0],[2, 2],[0, 2]and their respective sums are:-2, -1, 2.

Discussion

Method

LeetCode

public int countRangeSum(int[] nums, int lower, int upper) {
    int n = nums.length;
    long[] sums = new long[n + 1];
    for (int i = 0; i < n; ++i)
        sums[i + 1] = sums[i] + nums[i];
    return countWhileMergeSort(sums, 0, n + 1, lower, upper);
}

private int countWhileMergeSort(long[] sums, int start, int end, int lower, int upper) {
    if (end - start <= 1) return 0;
    int mid = (start + end) / 2;
    int count = countWhileMergeSort(sums, start, mid, lower, upper) 
              + countWhileMergeSort(sums, mid, end, lower, upper);
    int j = mid, k = mid, t = mid;
    long[] cache = new long[end - start];

    for (int i = start, r = 0; i < mid; ++i, ++r) {
        //注意，这里的循环在sums[k/j/t] 在一定条件下就break
        //意味着start to mid, mid to end 两部分一定要sorted
        while (k < end && sums[k] - sums[i] < lower) k++;
        while (j < end && sums[j] - sums[i] <= upper) j++;
        //这部分保证了在merge的时候，sums是sorted，因为sums[I] 是shorted
        while (t < end && sums[t] < sums[i]) cache[r++] = sums[t++];
        cache[r] = sums[i];
        count += j - k;
    }
    System.arraycopy(cache, 0, sums, start, t - start);
    return count;
}