照着人家的写了一个,原文解释的很详细了,稍微改了改。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | public class Solution { public int countRangeSum( int [] nums, int lower, int upper) { if (nums == null || nums.length == 0 ) return 0 ; long [] prefixSum = new long [nums.length]; prefixSum[ 0 ] = nums[ 0 ]; for ( int i = 1 ; i < nums.length; i++) prefixSum[i] = prefixSum[i- 1 ] + nums[i]; return mergeCount(prefixSum, 0 , nums.length - 1 , lower, upper); } private int mergeCount( long [] prefixSum, int start, int end, int lower, int upper) { if (start == end) { if (prefixSum[start] >= lower && prefixSum[start] <= upper) return 1 ; else return 0 ; } int mid = (start + end) / 2 ; int count = mergeCount(prefixSum, start, mid, lower, upper); count += mergeCount(prefixSum, mid + 1 , end, lower, upper); long [] left = new long [mid - start + 1 ]; long [] right = new long [end - mid]; for ( int i = 0 ; i < mid - start + 1 ; i++) left[i] = prefixSum[start + i]; for ( int i = 0 ; i < end - mid; i++) right[i] = prefixSum[mid + 1 + i]; for ( int leftIndex = 0 , lowerBound = 0 , upperBound = 0 , rightIndex = 0 , index = start; leftIndex < mid - start + 1 ; leftIndex++) { while (lowerBound < end - mid && right[lowerBound] - left[leftIndex] < lower) lowerBound++; while (upperBound < end - mid && right[upperBound] - left[leftIndex] <= upper) upperBound++; count += upperBound - lowerBound; while (rightIndex < end - mid && right[rightIndex] < left[leftIndex]) prefixSum[index++] = right[rightIndex++]; prefixSum[index++] = left[leftIndex]; } return count; } } |