LeetCode [327] Count of Range Sum

327. Count of Range Sum

Hard

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:

Input: nums = [-2,5,-1], lower = -2, upper = 2,
Output: 3 
Explanation: The three ranges are : [0,0], [2,2], [0,2] and their respective sums are: -2, -1, 2.

 

Constraints:

• 0 <= nums.length <= 10^4

//C++
//C++: TLE Divide and Conquer
class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        if(nums.empty() || lower>upper) return 0;
        int n = nums.size();
        if(n==1) return nums[0]>=lower&&nums[0]<=upper?1:0;
        vector<int> left(nums.begin(), nums.begin()+n/2);
        vector<int> right(nums.begin()+n/2, nums.end());
        int nl = countRangeSum(left, lower, upper);
        int nr = countRangeSum(right, lower, upper);

        for(int i=left.size()-2; i>=0; --i){
            left[i] += left[i+1];
        }
        for(int i=1; i<right.size(); ++i){
            right[i] += right[i-1];
        }
        sort(right.begin(), right.end());

        int c = 0;
        for(auto e:left){
            int a = lower-e, b = upper-e;
            int l = 0, r = right.size()-1;
            while(l<=r){
                if(right[l]<a){
                    l++;
                }else if(right[r]>b){
                    r--;
                }else{
                    break;
                }
            }
            c += r-l+1;
        }
        return c+nl+nr;
    }
};
]]></script>

<script class="brush: js" type="syntaxhighlighter"><![CDATA[
//C++: 72ms
typedef long long ll;

class Solution {
public:
    vector<ll> dm(vector<ll> nums, int lower, int upper, int &ret){
        int n = nums.size();
        if(n<2) return nums;
        vector<ll> left = dm(vector<ll>(nums.begin(), nums.begin()+n/2), lower, upper, ret);
        vector<ll> right = dm(vector<ll>(nums.begin()+n/2, nums.end()), lower, upper, ret);
        int nl = left.size(), nr = right.size(), t = 0, i = 0, j = 0, k = 0, index=-1;
        vector<ll> merge(n);
        for(; i<nl; ++i){
            while(j<nr && right[j]-left[i]<lower) j++;
            while(k<nr && right[k]-left[i]<=upper) k++;
            ret += k-j;
            while(t<nr && right[t]<=left[i]){
                merge[++index] = right[t++];
            }
            merge[++index] = left[i];
        }
        while(index<n-1){
            merge[++index] = right[t++];
        }
        return merge;
    }


    int countRangeSum(vector<int>& nums, int lower, int upper) {
        int ret = 0, n =  nums.size()+1;
        vector<ll> sums(n, 0);
        for(int i=1; i<n; ++i) sums[i] = sums[i-1] + nums[i-1];
        dm(sums, lower, upper, ret);
        return ret;
    }
};

//Java
class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        int n = nums.length;
        long[] array = new long[n+1];
        for(int i=1; i<=n; ++i){
            array[i] = array[i-1] + nums[i-1];
        }
        return helper(array, 0, n, lower, upper);
    }

    int helper(long[] array, int start, int end, int lower, int upper){
        if(end-start+1<2) return 0;
        int mid = (start+end)/2, count = 0;
        count += helper(array, start, mid, lower, upper);
        count += helper(array, mid+1, end, lower, upper);

        int j = mid+1, k = mid+1, l = mid+1, m = 0;
        long[] cache = new long[end-start+1];
        for(int i=start; i<=mid; ++i){
            while(j<=end && array[j]-array[i]<lower) j++;
            while(k<=end && array[k]-array[i]<=upper) k++;
            count += k-j;
            while(l<=end && array[l]<=array[i]) cache[m++] = array[l++];
            cache[m++] = array[i];
        }

        System.arraycopy(cache, 0, array, start, m);
        return count;
    }
}