Java Solution, beats 100%


  • 0
    I

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

Log in to reply
 

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