Sharing my 84ms C++ solution using merge sort


  • 3
    T
    class Solution {
    private:
        vector<long long int> merge(vector<long long int>& nums, int start, int mid, int end)
        {
            int i = start;
            int j = mid+1;
            vector<long long int> result;
            while(true)
            {
                if(i==mid+1)
                {
                    while(j<=end)
                    {
                        result.push_back(nums[j]);
                        j++;
                    }
                    break;
                }
                
                else if(j==end+1)
                {
                    while(i<=mid)
                    {
                        result.push_back(nums[i]);
                        i++;
                    }
                    break;
                }
                else
                {
                    if(nums[i]<nums[j])
                    {
                        result.push_back(nums[i]);
                        i++;
                    }
                    else
                    {
                        result.push_back(nums[j]);
                        j++;
                    }
                }
            }
            
            return result;
        }
        
        int mergeSort(vector<long long int>& sums, int start, int end, int lower, int upper)
        {
            if(start>end)
                return 0;
            else if(start==end)
            {
                if(sums[start]>=lower && sums[end]<=upper)
                    return 1;
                else
                    return 0;
            }
            
            int mid = (start+end)/2;
            int result = mergeSort(sums, start, mid, lower, upper)+mergeSort(sums, mid+1, end, lower, upper);
            int i, j, k;
            for(i=start, j=k=mid+1; i<=mid; i++)
            {
                while(j<=end && (sums[j]-sums[i])<lower) ++j;
                while(k<=end && (sums[k]-sums[i]<=upper)) ++k;
                result = result + (k-j);
            }
            
            vector<long long int> temp = merge(sums, start, mid, end);
            for(i=start; i<=end; i++)
                sums[i] = temp[i-start];
                
            return result;
        }
    public:
        int countRangeSum(vector<int>& nums, int lower, int upper) {
            int n = nums.size(), i;
            if(n==0)
                return 0;
            vector<long long int> sums(n, 0);
            sums[0] = nums[0];
            for(i=1; i<n; i++)
                sums[i] = sums[i-1] + nums[i];
            return mergeSort(sums, 0, n-1, lower, upper);
        }
    };

  • -1
    This post is deleted!

Log in to reply
 

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