merge sort solution


  • 0
    D

    this is my first post, this method is a little bit complexity, it takes 39ms time.
    i use top down merge sort way and this is the merge sort code

    int ret, _k;
    void merge(vector<int> &sum, vector<int> &t, int a, int mid, int b) {
    	int i = a, j = mid + 1, k = a;
    	while (i <= mid && j <= b) {
    		if (_k >= 0)
    			if (t[i] <= t[j]) {
    			    sum[k++] = t[i];
        			int x = j;
    			    while (x <= b && t[i] >= (t[x] - _k)) {
    			        if (t[i] == (t[x] - _k)) ret++;
    			        x++;
    			    }
        			i++;
    			} else sum[k++] = t[j++];
    		else {
    			if (t[i] >= t[j]) {
    			    sum[k++] = t[i];
        			int x = j;
    			    while (x <= b && t[i] <= (t[x] - _k)) {
    			        if (t[i] == (t[x] - _k)) ret++;
    			        x++;
    			    }
        			i++;
    			} else sum[k++] = t[j++];
    		}
    	}
    	while (i <= mid) {
    		sum[k++] = t[i++];
    	}
    	while (j <= b) {
    		sum[k++] = t[j++];
    	}
    }
    void mergeSort(vector<int> &sum, vector<int> &t, int a, int b) {
    	if (a >= b) return;
    	int mid = a + (b - a) / 2;
    	mergeSort(t, sum, a, mid);
    	mergeSort(t, sum, mid + 1, b);
    	merge(sum, t, a, mid, b);
    }
    int subarraySum(vector<int>& nums, int k) {
    	ret = 0;
    	_k = k;
        vector<int> sum(nums.size()+1, 0);
        vector<int> t(nums.size()+1, 0);
        for (int i = 0; i < nums.size(); i++) {
        	sum[i + 1] = sum[i] + nums[i];
        	t[i + 1] = sum[i + 1];
        }
    	mergeSort(sum, t, 0, t.size() - 1);
    	return ret;
    }
    

  • 0
    X

    @david_shi Could you explain how does your code work? Thanks.


Log in to reply
 

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