327. Count of Range Sum

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ? j), inclusive.

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

Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.

一刷
题解：
方法1: naive
先构造一个sum array,sum[i+1]表示[0,i]的sum, 然后做二维loop, time complexity O(n^2)
注意sum array是long型。避免溢出。

class Solution {
    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];
        }
        int ans = 0;
        for(int i=0; i<n; i++){
            for(int j=i+1; j<=n; j++){
                if(sums[j] - sums[i]>= lower && sums[j] - sums[i]<= upper) ans++;
            }
        }
        return ans;
    }
}

出现超时。

方法2：利用merge sort
对于两列array1, array2
i在array1 中遍历， 然后用两个数在array2j, k中遍历，找到第一个nums[i] + nums[j]>lower, 第一个nums[i] + nums[k]>upper，那么j-k中间的值都满足条件。
i++, j, k继续从刚才停下来的地方继续
注意，我们创建cache数组，保存merge后的值，然后将cache复制给sum

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) {
        while (k < end && sums[k] - sums[i] < lower) k++;
        while (j < end && sums[j] - sums[i] <= upper) j++;
        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;
}