8 lines concise c++ code with explanation


  • 1
    Z

    The idea come from Max Sum of Sub-Matrix No Larger Than K.

    int countRangeSum(vector<int>& nums, int lower, int upper) {
            long long sum=0,ret=0;
            multiset<long long> accum={0};
            for(auto x:nums){
                sum+=x;
                auto start=accum.lower_bound(sum-upper),end=accum.upper_bound(sum-lower);
                while(start!=end) ret++,start++;
                accum.insert(sum);
            }
            return ret;
        }
    

    explanation:
    let range sum between j+1 and i be sum[j][i](j<i),range sum from 0 to i be sum[i].
    if lower<=sum[j][i]<=upper,then lower<=sum[i]-sum[j]<=upper.
    then we have

    • sum[i]-sum[j]<=upper
    • sum[i]-sum[j]>=lower

    thus we can search for sum[j] as below:

    • lower_bound:sum[j]>=sum[i]-upper---use lower_bound() to search for the first previous sum that is no less than sum[i]-upper.
    • upper_bound:sum[j]>sum[i]-lower---use upper_bound() to search for the first previous sum that is bigger than sum[i]-lower.

    the time complexities of insert(),upper_bound() and lower_bound() are O(logn).


  • 0

    That's not O(n log n). Because you're counting the ranges one by one and their number isn't O(n log n).


  • 0
    Z

    Yeah,my fault again,thanks for correct.


  • 0

    @zoharlee Quite clean solution, thanks for sharing. Voting you up!


  • 0
    W

    The naive method iterator an array n^2 times
    Your method iterator the RB-tree n^2 times

    worse than the naive method...


  • 0

    @zoharlee
    use distance can make your code become a little bit quick.
    Nice solution anyway.

    class Solution {
    public:
        int countRangeSum(vector<int>& nums, int lower, int upper) {
            long long offset=0,subsum=0;
            multiset<long long> ms = {0};
            for(int i=0;i<nums.size();i++){
                offset+=nums[i];
                auto itlow=ms.lower_bound(offset - upper),itup=ms.upper_bound(offset - lower);
                subsum+=distance(itlow,itup);
                ms.insert(offset);
            }
            return (int)(subsum);
        }
    };
    

Log in to reply
 

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