Java Solution, beats 100%

• Just a variation of merge sort

``````class Solution {
public int subarraySum(int[] nums, int k) {
final long[] sums = new long[nums.length+1];
for(int i=0; i<nums.length; i++) {
sums[i+1] = sums[i] + nums[i];
}
return mergeSort(sums, 0, nums.length, k, new long[nums.length/2+1]);
}

//[st, ed]
private int mergeSort(final long[] sums, final int st, final int ed, final int k, final long[] paper) {
if (st == ed) return 0;
final int mid = (st+ed)/2;
int ans = mergeSort(sums, st, mid, k, paper) + mergeSort(sums, mid+1, ed, k, paper);
for(int i=st, j=mid+1; i<=mid && j<=ed; i++) {
while(j <= ed && sums[j] < k+ sums[i]) j++;
if (j<=ed && sums[j] == k+sums[i]) {
int t=j+1;
while(t<=ed && sums[t] == sums[j]) t++;
ans += t-j;
}
}
final int len = mid-st+1;
System.arraycopy(sums, st, paper, 0, len);
int p = 0, i = st;
for(int q = mid+1; p < len && q <= ed;) {
sums[i++] = paper[p] <= sums[q] ? paper[p++] : sums[q++];
}
while(p<len) sums[i++] = paper[p++];
return ans;
}
}
``````

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