327. Count of Range Sum

The naive solution takes O(n*n) time.

1:  class Solution {  
2:  public:  
3:    int countRangeSum(vector<int>& nums, int lower, int upper) {  
4:      int res = 0;  
5:      for (int i = 0; i < nums.size(); i++) {  
6:        long long sum = 0;  
7:        for (int j = i; j < nums.size(); j++) {  
8:          sum += nums[j];  
9:          if (sum >= lower && sum <= upper) res++;  
10:        }  
11:      }  
12:      return res;  
13:    }  
14:  };  

The other way is to try merge sort. However, instead of sorting numbers here, we sort the sums. So we need to preprocess the numbers first to get a sum array. For the sum array, the range sum between nums[i] and nums[j] is straightforward, i.e. sums[j] - sums[i]. So for the merge sort, we only need to find pairs (i, j) across two sorted partitions such that sums[j] - sum[i] is smaller than or equal to the given interval. Note, we need to be careful about overflow because when you compute the sum, INT_MAX - (-1) gets overflow. So the sums array should use long integer.

1:  class Solution {  
2:  public:  
3:    int countRangeSum(vector<int>& nums, int lower, int upper) {  
4:      vector<long long> sums(nums.size()+1, 0);  
5:      for (int i = 1; i <= nums.size(); i++) {  
6:        sums[i] = sums[i-1]+nums[i-1];  
7:      }  
8:      return mergeSort(sums, 1, nums.size(), lower, upper);  
9:    }  
10:    int mergeSort(vector<long long> &sums, int l, int r, int lower, int upper) {  
11:      if (l > r) return 0;  
12:      if (l == r) return sums[l] >= lower && sums[r] <= upper ? 1 : 0;  
13:      int mid = l + (r-l) / 2;  
14:      int res = mergeSort(sums, l, mid, lower, upper) + mergeSort(sums, mid+1, r, lower, upper);  
15:      int i = 0, j = 0, k = 0;  
16:      for (int i = l, j = k = mid+1; i <= mid; i++) {  
17:        while (j <= r && sums[j]-sums[i] < lower) j++;  
18:        while (k <= r && sums[k]-sums[i] <= upper) k++;  
19:        res += k-j;  
20:      }  
21:      vector<long long> tmp(r-l+1, 0);  
22:      i = l;  
23:      j = mid+1;  
24:      for (k = l; i <= mid && j <= r; k++) {  
25:        if (sums[i] < sums[j]) tmp[k-l] = sums[i++];  
26:        else tmp[k-l] = sums[j++];  
27:      }  
28:      while (i <= mid) tmp[k++-l] = sums[i++];  
29:      while (j <= r) tmp[k++-l] = sums[j++];  
30:      for (int k = l; k <= r; k++) {  
31:        sums[k] = tmp[k-l];  
32:      }  
33:      return res;  
34:    }  
35:  };