C++ solution with insertion sort


  • 0
    C
    class Solution {
    public:
        int countRangeSum(vector<int>& nums, int lower, int upper) {
            long sub_sum = 0;
            vector<long> sorted(1, 0);
            int res = 0;
            for ( int i = 0; i < int(nums.size()); i++ ) {
                sub_sum += nums[i];
                int lbd = lower_bound(sorted.begin(), sorted.end(), sub_sum - upper) - sorted.begin();
                int ubd = upper_bound(sorted.begin(), sorted.end(), sub_sum - lower) - sorted.begin() - 1;
                res += ubd - lbd + 1;
                int newPos = upper_bound(sorted.begin(), sorted.end(), sub_sum) - sorted.begin();
                sorted.insert(sorted.begin() + newPos, sub_sum);
            }
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.