这一题,我们使用了分治法。
首先看时间复杂度为o(n^2),比较naïve的方法:
使用一个数组sum[],长度为原数组长度+1,每一个元素sum[i]为原数组中index0~i-1之和,显然当sum[j] – sum[i]就是i~j-1之和,于是我们只需要两个for来遍历所有[i, j],并且比较是否在lower~upper之间即可。
但是题目要求时间复杂度由于o(n^2),考虑使用分治
1) 分:将sum[]分为左右两部分,分别计算满足条件的[i,j]
2) 合:除了i,j都在左或者都在右,还有一种情况,i在左,j在右 想要复杂度为o(nlogn),由主方法易知,合这一步必须为线性复杂度。这里有一个小trick,在合这一步中我们对这一次迭代的sum[start]-sum[end]进行排序,这样,返回之后,对于上一层函数来说,左右两部分都已经排好了序,我们只需要检测i = start~mid,mid<j,k<=end然后找到第一个sum[k]-sum[i] > lower, 和第一个sum[j] – sum[i] > upper,然后j-k就是满足条件的范围的个数。
代码如下:
1 class Solution { 2 public int countRangeSum(int[] nums, int lower, int upper) { 3 long[] sum = new long[nums.length+1]; 4 5 for(int i=0; i<nums.length; i++){ 6 sum[i+1] = sum[i] + nums[i]; 7 } 8 9 return mergeSort(sum, 0, nums.length + 1, lower, upper); 10 } 11 12 private int mergeSort(long[] sum, int start, int end, int lower, int upper){ 13 if(end - start <= 1) 14 return 0; 15 int mid = start + (end - start) / 2; 16 //int mid = (start + end) / 2; 17 int count = mergeSort(sum, start, mid, lower, upper) + mergeSort(sum, mid, end, lower, upper); 18 19 long[] tmp = new long[end - start]; 20 int j = mid, k = mid, t = mid; 21 for(int i = start, r = 0; i < mid; i++, r++){ 22 while(k < end && sum[k] - sum[i] < lower) 23 k++; 24 while(j < end && sum[j] - sum[i] <= upper) 25 j++; 26 while(t < end && sum[t] < sum[i]) 27 tmp[r++] = sum[t++]; 28 tmp[r] = sum[i]; 29 30 count += j - k; 31 } 32 33 System.arraycopy(tmp, 0, sum, start, t - start); 34 return count; 35 } 36 }