8 line C++ with multiset runs 104ms beats 30%


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

  • 0
    R

    Can u please explain your solution?

    Thanks in advance.


  • 1
    Z

    I tried this solution too.
    distance(itlow, itup) uses a for loop to calculate the distance, so the algorithm becomes O(n^2logn) in the worst case.


  • 0
    Y

    Thank your code, it makes me learned the function distance. At first I wanted to use operator - to calculate the distance between two iterators, however the feedback was compile error. So I decided to see the discuss, maybe I can find some similar solution which also uses multiset. Really I found it. By the way in multiset it calculate distance using operator ++, the time complexity is O(n), be careful. Good luck to you .


  • 0
    F

    I think the worst case should be O(n*(n + 2*n + n)) = O(n^2)


  • 0
    Z

    My mistake. The worst case is O(n(logn + 2logn + n)) = O(n^2)


  • 0
    F

    The correct analysis of its complexity is actually O(nlogn) + K, which K is the output of the algorithm. So this algorithm's complexity depends on its output. There are many other algorithm that falls into this category too.


  • 0
    C

    Just explain the solution. The element of the set multiset is the sum of the first n elements in nums . Suppose that x is the element of the set and the next added element of the set is y. And a represents lower and b represents upper. The number of x that satisfies a<=y-x<=b is the value of function distance(). Before we do some thing, change the form a<=y-x<=b and get y-b<=x<=y-a. The soltution is that

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

Log in to reply
 

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