[LeetCode]: 327. Count of Range Sum

https://leetcode.com/problems/count-of-range-sum/#/description

Solution:
This is an interesting question. As stated in the introduction, the O(n2) method is not accepted. So we need to find a faster way. For this question, we are look for ranges that satisfy:
                          sum[i to j] = sum[0 to j] - sum[0 to i] >= lower; and
                          sum[i to j] = sum[0 to j] - sum[0 to i] <= upper
which can be further re-wrote as:
                         sum[0 to i] <= sum[0 to j] - lower; and
                         sum[0 to i] >= sum[0 to j] - upper.
Now it becomes clear that once we have sum[0 to i] where 0<=i<n (which can be obtained easily with O(n)), we can calculate the elements numbers by just looking the range of [sum[0 to j] - upper, sum[0 to j] - lower]. In order to avoid the re-counting, we can count the number of elements in the process of constructing the sorted array of sum[0 to i]. In this way, all the ranges found have at least one unique end. We also need to do the counting before inserting the element sum[0 to i] into the sorted array, to avoid the case that the sum[0 to i] locates just between [sum[0 to j] - upper, sum[0 to j] - lower]. (in this case, we will mistakenly count the elements by 1 more.)

Some details:
1):We also need to consider the sum[0 to i] itself, which can be elegantly solving by add a '0' element inside the sorted array in the beginning.
2): the long type can be used to avoid overflow problem.

The key point is by constructing a sorted array, the complexity can be reduced from O(n2) to O(nlnn). See code below:

Code:

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        int res = 0;
        int n = nums.size();
        if(n==0) return res;
        vector<long> sums;
        sums.push_back(0);
        long sum = 0;
        for(int i=0; i<nums.size(); ++i){
            sum += nums[i];
            int left = findLeftPosition(sums, sum-upper);
            int right = findRightPosition(sums, sum-lower);
            res += right - left;
            int ind = findLeftPosition(sums, sum);
            sums.insert(sums.begin()+ind, sum);
        }
        return res;
    }
private:
    int findLeftPosition(vector<long> &s, long a){
        int left = 0, right = s.size();
        while(left < right){
            int m = left + (right - left)/2;
            if(s[m]<a) left = m+1;
            else right = m;
        }
        return left;
    }
    int findRightPosition(vector<long> &s, long a){
        int left = 0, right = s.size();
        while(left < right){
            int m = left + (right - left)/2;
            if(s[m]<=a) left = m + 1;
            else right = m;
        }
        return left;
    }
};

The code can be further simplified by using lower_bound() and upper_bound() functions. See below: Code:

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        int res = 0, n = nums.size();
        vector<long> sums;
        sums.push_back(0);
        long sum = 0;
        for(int i=0; i<nums.size(); ++i){
            sum += nums[i];
            auto left = lower_bound(sums.begin(), sums.end(), sum-upper);
            auto right = upper_bound(sums.begin(), sums.end(), sum-lower);
            res += (int) (right - left);
            sums.insert(lower_bound(sums.begin(), sums.end(), sum), sum);
        }
        return res;
    }
};