[recommend for beginners] C++ implementations of the top-voted-solution


  • 4
    class Solution {
    public:
        /***   O(N^2)  Solution     ***/
        int countRangeSum(vector<int>& nums, int lower, int upper) {
            int size_nums=nums.size();
            vector<long> sums(size_nums+1, 0);
            for(int i=0; i<size_nums; i++){
                sums[i+1]=sums[i]+nums[i];
            }
            int result=0;
            for(int i=0; i<size_nums; i++){
                for(int j=i+1; j<=size_nums; j++){
                    int temp=sums[j]-sums[i];
                    if(temp >= lower && temp <= upper)  result++;
                }
            }
            return result;
        }
        
        /***   O(N*logN)  Solution     ***/
        int countRangeSum(vector<int>& nums, int lower, int upper) {
            int size_nums=nums.size();
            vector<long> sums(size_nums+1, 0);
            for(int i=0; i<size_nums; i++)   sums[i+1]=sums[i]+nums[i];
            return help(sums, 0, size_nums+1, lower, upper);
        }
        
        int help(vector<long> &sums, int start, int end, int lower, int upper){
            /***  end condition  ***/
            if(end - start <= 1) return 0;
            /***  recursive devidely  ***/
            int mid=(start+end)/2;
            int count=help(sums, start, mid, lower, upper)
                    + help(sums, mid, end, lower, upper);
            int j=mid, k=mid, t=mid;
            vector<long> cache(end-start, 0);
            for(int i=start, r=0; i<mid; i++, r++){
                while(k<end && sums[k]-sums[i] < lower) k++;
                while(j<end && sums[j]-sums[i] <= upper) j++;
                /***  merge sorting parts  ***/
                while(t<end && sums[t] < sums[i])  cache[r++]=sums[t++];
                cache[r]=sums[i];
                count+=j-k;
            }
            //copy the merge sorted array to the original sums
            for(int i=0; i<t-start; i++)  sums[start+i]=cache[i];
            return count;
        }
    };

  • 0
    class Solution {
    public:
        int countRangeSum(vector<int>& nums, int lower, int upper) {
            int _size=nums.size();
            if(_size==0)  return 0;
            int result=0;
            vector<int> sum(_size+1, 0);
            for(int i=1; i<=_size; i++){
                sum[i]=sum[i-1]+nums[i-1];
            }
            for(int i=0; i<=_size-1; i++){
                for(int j=i+1; j<=_size; j++){
                    int temp=sum[j]-sum[i];
                    if(temp>=lower && temp<=upper) result++;
                }
            }
            return result;
        }
    };

  • 0

    this method is by building a binary-prefix-sum-tree. The root record sum[0,0], the other node in the tree record sum[0, i] in the binary search form.
    So when we search the

            #CNT =  sum[i]-sum[j] (j<i)   subject to.    lower <=sum[i]-sum[j] <= upper
    

    For each sum[i], we can do the search in O(logN) time. so the overall time is

         O(logN*N)
    

    Here is the code : we count the #CNT ended by sum[i] i=1...n

      class Node{
        public:
            long long val;
            int cnt;
            Node *left, *right;
            Node(long long v):val(v), cnt(1), left(NULL), right(NULL) {}
        };
        
        class Tree{
        public:
            Tree():root(NULL){}
            ~Tree() { freeTree(root); }
            
            void Insert(long long val){
                Insert(root, val);
            }
            
            int  LessThan(long long sum, int val){
                return LessThan(root, sum, val, 0);
            }
        
        private:
            Node* root;
            void Insert(Node* &root, long long val){
                if(!root){
                    root=new Node(val);
                    return;
                }
                root->cnt++;
                if(val<root->val){
                    Insert(root->left, val);
                }else if(val>root->val){
                    Insert(root->right, val);
                }
            }
            
            int LessThan(Node* root, long long sum, int val, int res){
                if(!root)  return res;
                if(sum-root->val < val){
                    res+=(root->cnt-(root->left ? root->left->cnt : 0));
                    return LessThan(root->left, sum, val, res);
                }else if(sum-root->val > val){
                    return LessThan(root->right, sum, val, res);
                }else{
                    return res+(root->right ? root->right->cnt : 0);
                }
            }
            
            void freeTree(Node* root){
                if(!root) return;
                if(root->left)  freeTree(root->left);
                if(root->right) freeTree(root->right);
                delete root;
            }
        };
        
        class Solution {
        public:
            int countRangeSum(vector<int>& nums, int lower, int upper) {
                Tree tree;
                tree.Insert(0);
                long long sum=0;
                int res=0;
                for(int n:nums){
                    sum+=n;
                    int lcnt=tree.LessThan(sum, lower);
                    int hcnt=tree.LessThan(sum, upper+1);
                    res+=(hcnt-lcnt);
                    tree.Insert(sum);
                }
                return res;
            }
        };

  • 1
    class Solution {
    public:
        int countRangeSum(vector<int>& nums, int lower, int upper) {
            int size=nums.size();
            if(size==0)  return 0;
            vector<long> sums(size+1, 0);
            for(int i=0; i<size; i++)  sums[i+1]=sums[i]+nums[i];
            return help(sums, 0, size+1, lower, upper);
        }
        
        /*** [start, end)  ***/
        int help(vector<long>& sums, int start, int end, int lower, int upper){
            /*** only-one-element, so the count-pair=0 ***/
            if(end-start<=1)  return 0;
            int mid=(start+end)/2;
            int count=help(sums, start, mid, lower, upper)
                    + help(sums, mid, end, lower, upper);
            
            int m=mid, n=mid, t=mid, len=0;
            /*** cache stores the sorted-merged-2-list ***/
            /*** so we use the "len" to record the merged length ***/
            vector<long> cache(end-start, 0);
            for(int i=start, s=0; i<mid; i++, s++){
                /*** wrong code: while(m<end && sums[m++]-sums[i]<lower);  ***/
                while(m<end && sums[m]-sums[i]<lower) m++;
                while(n<end && sums[n]-sums[i]<=upper) n++;
                count+=n-m;
                /*** cache will merge-in-the-smaller-part-of-list2 ***/
                while(t<end && sums[t]<sums[i]) cache[s++]=sums[t++];
                cache[s]=sums[i];
                len=s;
            }
            
            for(int i=0; i<=len; i++)  sums[start+i]=cache[i];
            return count;
        }
    };

  • 2
    2

    This problem can be solved in O(NlogN) using the merging sorting based method ..

    233333333333

    Code :

    class Solution {
    public:
        int countRangeSum(vector<int>& nums, int lower, int upper) {
            int size_nums = nums.size();
            vector<long> sums(size_nums+1, 0);
            for(int i = 0; i < size_nums; i++) {
                sums[i+1] = sums[i] + nums[i];
            }
            return help(sums, 0, size_nums+1, lower, upper);
        }
        
        /** end is open field [start, end) **/
        int help(vector<long>& sums, int start, int end, int lower, int upper) {
            if(end - start <= 1)  return 0;
            int mid = (start + end) / 2;
            int count = help(sums, start, mid, lower, upper) + help(sums, mid, end, lower, upper);
            
            int left = mid, right = mid, cur = mid;
            
            vector<long> cache(end - start, 0);
            int cache_index = 0;
            for(int i = start, j = mid; i < mid; i++) {
                while(left < end && sums[left] - sums[i] < lower)  left++;
                while(right < end && sums[right] - sums[i] <= upper) right++;
                /** merge sort only put the smaller number before **/
                while(j < end && sums[i] >= sums[j])  cache[cache_index++] = sums[j++];
                cache[cache_index++] = sums[i];
                count += (right - left);
            }
            
            for(int i = 0; i < cache_index; i++) {
                sums[start + i] = cache[i];
            }
            
            return count;
        }
    };

  • 0
    2

    Here is a solution refered to the Lintcode ..

    The key idea is to use the

    lower_bound    &    upper_bound
    

    To find all the index that sum range smaller than the start value, which is the left iterator.
    Similarly , we find the index the sum range smaller than the end value, which is the right iterator.
    So the range [left + 1, right] is just the range satisify the condition.

    class Solution {
    public:
        /**
         * @param A an integer array
         * @param start an integer
         * @param end an integer
         * @return the number of possible answer
         */
        int subarraySumII(vector<int>& A, int start, int end) {
            // sum_from_start[i] denotes sum for 0 ~ i - 1.
            vector<int> sum_from_start(A.size() + 1);
            partial_sum(A.cbegin(), A.cend(), sum_from_start.begin() + 1);
    
            int result = 0;
            for (int j = 0; j < A.size(); ++j) {
                const auto left = lower_bound(sum_from_start.cbegin(),
                                              sum_from_start.cbegin() + j + 1,
                                              sum_from_start[j + 1] - end);
                const auto right = upper_bound(sum_from_start.cbegin(),
                                               sum_from_start.cbegin() + j + 1,
                                               sum_from_start[j + 1] - start);
                result += (right - sum_from_start.cbegin()) - 
                          (left - sum_from_start.cbegin());
            }
    
            return result;
        }
    };

  • 0
    A

    Your solution is incorrect, lower_bound works only on a sorted array.


  • 1
    F

    I strong recommend this multiset based solution !!!

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

  • 0
    Z

    @RainbowSecret I would say your solution is too complex.


  • 0
    Z

    @fight.for.dream I think this solution is still O(n^2), because although lower_bound/upper_bound method is O(logn), the distance operation for multiset is O(n). Then the total complexity is still O(n^2).


Log in to reply
 

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