327. Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.

Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.

Note:

A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example:

Given nums = [-2, 5, -1], lower = -2, upper = 2,

Return 3.

The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.

Credits:

Special thanks to @dietpepsi for adding this problem and creating all test cases.

My naive approach gets me TLE, as expected.

//This naive O(n^2) algorithm of course gets me TLE public int countRangeSum_my_naive_way(int[] nums, int lower, int upper) { Set<String> uniqueRangeSums = Sets.newHashSet(); StringBuilder sb = new StringBuilder(); for(int i = 0; i < nums.length; i++){ long sum = nums[i]; if(sum >= lower && sum <= upper) uniqueRangeSums.add(sb.append("" + i + i).toString()); sb.setLength(0); for(int j = i+1; j < nums.length; j++){ sum += nums[j]; if(sum >= lower && sum <= upper) uniqueRangeSums.add(sb.append("" + i + j).toString()); sb.setLength(0); } } return uniqueRangeSums.size(); }

Then looked at dietpepsi’s post: https://discuss.leetcode.com/topic/33738/share-my-solution

I didn’t sort out my logic following his ideas yet. [TODO] completely understand it.

public int countRangeSum(int[] nums, int lower, int upper) { int n = nums.length; long[] sums = new long[n+1]; for(int i = 0; i < n; i++){ sums[i+1] = sums[i] + nums[i]; } return countWhileMergeSort(sums, 0, n+1, lower, upper); } private int countWhileMergeSort(long[] sums, int start, int end, int lower, int upper) { if(end - start <= 1) return 0; int mid = (start+end)/2; int count = countWhileMergeSort(sums, start, mid, lower, upper) + countWhileMergeSort(sums, mid, end, lower, upper); int j = mid, k = mid, t = mid; long[] cache = new long[end-start]; for(int i = start, r = 0; i < mid; i++, r++){ while(k < end && sums[k] - sums[i] < lower) k++; while(j < end && sums[j] - sums[i] <= upper) j++; while(t < end && sums[t] < sums[i]) cache[r++] = sums[t++]; cache[r] = sums[i]; count += j-k; } System.arraycopy(cache, 0, sums, start, t-start); return count; }