题目

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.

解法

因为我们要用排序来优化求解过程，但是排序之后的数组是不能用来求解的，这样我们就采用归并排序的思想，在排序之前求出左右两边数组的个数，然后再求整体的。 这里我们的排序对象是前缀求和数组，在归并排序的合并阶段，我们有左数组和右数组，且左和右数组都是排好序的，所以我们可以用i遍历左数组，j，k两个指针分别取在右数组搜索，使得：

sums[j] - sums[i] < upper sums[k] - sums[i] >= lower 那么此时，我们就找到了j-k个符合要求的子数组。

由于左右数组都是排好序的，所以当i递增之后，j和k的位置不用从头开始扫描。

最后还有一点需要注意的就是，为了防止溢出，我们的vector容纳的是long long型元素。

代码

class Solution { public: long long sum[100000]; long long tmp[100000]; int gao( int st, int ed, int lower, int upper ){ if( st >= ed ) return 0; int mid = st + ( ed - st ) / 2; int cnt = gao( st, mid, lower, upper ) + gao( mid + 1, ed, lower, upper ); int j = mid + 1, k = mid + 1; for( int i = st; i <= mid; i++ ){ while( j <= ed && sum[j] - sum[i] <= upper ) j++; while( k <= ed && sum[k] - sum[i] < lower ) k++; cnt += j - k; } int p = st, q = mid + 1, t = st; while( p <= mid && q <= ed ){ if( sum[p] <= sum[q] ){ tmp[t++] = sum[p++]; }else{ tmp[t++] = sum[q++]; } } while( p <= mid ){ tmp[t++] = sum[p++]; } while( q <= ed ){ tmp[t++] = sum[q++]; } for( int i = st; i <= ed; i++ ){ sum[i] = tmp[i]; } return cnt; } int countRangeSum(vector<int>& nums, int lower, int upper) { sum[0] = 0; for( int i = 0; i < (int)nums.size(); i++ ){ sum[i+1] = sum[i] + nums[i]; } return gao( 0, (int)nums.size(), lower, upper ); } };