[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;
    }
}; 

[LeetCode]: 544. Output Contest Matches

https://leetcode.com/contest/leetcode-weekly-contest-24/problems/output-contest-matches/

Solution:
This question is pretty straightforward: will used string vector to store the initial array, then gradually combine them by adding the first one with the last one, ... until only one array left. See code below: 

Code:

class Solution {
public:
    string findContestMatch(int n) {
        if(n<2) return"";
        vector<string> res;
        for(int i=1; i<=n; ++i){
            res.push_back(to_string(i));
        }
        while(res.size()>1){
            int t = res.size();
            for(int i=0;i<t/2; ++i){
                res[i] = '(' + res[i] + ',' + res.back() + ')';
                res.pop_back();
            }
        }
        return res[0];
    }
};