share my complex mergesort code:)


  • 0
    S
    class Solution {
    public:
        int subarraySum(vector<int>& nums, int k) {
            vector<int>sum;
            int cnt=0;
            for(int i=0; i<nums.size(); ++i){
                cnt+=nums[i];
                sum.push_back(cnt);
            }
            return merge(sum, 0, nums.size()-1, k);
        }
        
        int merge(vector<int>& sum, int begin, int last, int k){
            if(begin==last)
                return sum[begin]==k;
            int mid=begin+(last-begin)/2;
            int res=merge(sum, begin, mid, k)+merge(sum, mid+1, last, k);
            vector<int>tmp;
            int i=begin, j=mid+1;
            while(i<=mid&&j<=last){
                if(sum[j]-sum[i]==k){
                    int l=i, r=j;
                    while(j<=last&&sum[j]==sum[r]){
                        j++;
                    }
                    while(i<=mid&&sum[i]==sum[l]){
                        i++;
                    }
                    res+=(r-j)*(l-i);
                }
                else if(sum[j]-sum[i]>k)
                    i++;
                else
                    j++;
            }
            i=begin;
            j=mid+1;
            while(i<=mid||j<=last){
                tmp.push_back(j>last||(i<=mid&&sum[i]<sum[j])?sum[i++]:sum[j++]);
            }
            for(i=begin; i<=last; ++i){
                sum[i]=tmp[i-begin];
            }
            return res;
        }
    };
    

Log in to reply
 

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