# merge sort solution

• 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;
}
``````

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

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