LeetCode 327. 区间和的个数（multiset二分查找/归并排序）数据结构与算法Michael是个半路程序员-

1. 题目

给定一个整数数组 nums，返回区间和在 [lower, upper] 之间的个数，包含 lower 和 upper。

区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

说明:
最直观的算法复杂度是 O(n2) ，请在此基础上优化你的算法。

示例: 输入: nums = [-2,5,-1], lower = -2, upper = 2, 输出: 3  解释: 3个区间分别是: [0,0], [2,2], [0,2]，它们表示的和分别为: -2, -1, 2。 

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/count-of-range-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

2.1 动态规划超时

• 区间动态规划，超时例子，复杂度太高
  $O(n^2)$

  O(n2)

• 整型溢出例子[2147483647,-2147483648,-1,0] -1 0
  

class Solution { public: int countRangeSum(vector<int>& nums, int lower, int upper) { if(nums.size() == 0) return 0; int i, j, len, n = nums.size(), count=0;      vector<vector<long>> dp(n,vector<long>(n,0)); //区间[i,j]的和 for(i = 0; i < n; ++i) {       dp[i][i] = nums[i]; if(lower<=dp[i][i] && dp[i][i]<=upper)        count++; } for(len = 1; len < n; ++len) { for(i = 0; i < n-len; ++i) {        dp[i][i+len] = dp[i][i+len-1] + dp[i+len][i+len]; if(lower<=dp[i][i+len] && dp[i][i+len]<=upper)         count++; } } return count; } }; 

2.2 二分查找

• 参考大佬的解法
• 前缀和 sum，
  $L le sum[j]-sum[i] le U Rightarrow sum[j]-Ule sum[i] le sum[j]-L$

  L≤sum[j]−sum[i]≤U⇒sum[j]−U≤sum[i]≤sum[j]−L

• j = 0 时, 上式 sum[i] = 0，sum[i] 可以看做前面的和， sum[j] 当前的和
• 以每个 j 点作为结束的区间，前面哪些 i 到 j 的和在范围内
• 将前次的前缀和插入multiset，有序，可以二分查找
• 查找set中前缀值在 当前 前缀和
  $sum[j]$

  sum[j] 上下范围内（
  $[sum[j]-U, sum[j]-L]$

  [sum[j]−U,sum[j]−L]）的个数

class Solution { public: int countRangeSum(vector<int>& nums, int lower, int upper) { if(nums.size() == 0) return 0;      multiset<long> s;         s.insert(0); int count = 0; long sum = 0; for(int i = 0; i < nums.size(); ++i) {       sum += nums[i];       count += distance(s.lower_bound(sum-upper), s.upper_bound(sum-lower));             s.insert(sum); } return count; } }; 

但是上面解法中distance在set中（不可随机访问）是 O(n)时间复杂度的，所以用数组进行二分查找两个端点，然后做差会更快些。
80 ms 14.4 MB

2.3 归并排序

• 其实归并排序求逆序度是本题的一个特例
• 对前缀和进行归并排序（注意头部要加一个0，用于第一个数的）
• 归并时，固定左边的一个端点，右边有两个指针进行遍历查找

核心代码段：

 int i = l, jlo = mid+1, jup = mid+1;//右侧两个指针 while(i <= mid)//遍历左侧的端点 { while(jlo <= r && sum[jlo]-sum[i] < lower)//[i,jlo]不在范围内                 jlo++; while(jup <= r && sum[jup]-sum[i] <= upper)//[i,jup]在范围内                 jup++; //最后 [jlo,jup) 为在范围内的右端点             count += jup-jlo;//计数             i++;//遍历下一个左端点 } 

class Solution {     vector<long> temp; public: int countRangeSum(vector<int>& nums, int lower, int upper) { if(nums.size() == 0) return 0;         vector<long> sum(nums.size()+1, 0);         temp.resize(nums.size()+1); for(int i = 1; i < sum.size(); ++i)             sum[i] = sum[i-1] + nums[i-1]; return mergeSort(sum,0,sum.size()-1,lower,upper); } int mergeSort(vector<long>& sum, int l, int r, int lower, int upper) { if(l >= r) return 0; int mid = l+((r-l)>>1), count = 0;         count += mergeSort(sum, l, mid, lower, upper);         count += mergeSort(sum, mid+1, r, lower, upper); int i = l, jlo = mid+1, jup = mid+1; while(i <= mid) { while(jlo <= r && sum[jlo]-sum[i] < lower)                 jlo++; while(jup <= r && sum[jup]-sum[i] <= upper)                 jup++;             count += jup-jlo;             i++; } //合并，跟归并排序一致         i = l; int j = mid+1, k = 0; while(i <= mid && j <= r) { if(sum[i] <= sum[j])                 temp[k++] = sum[i++]; else                 temp[k++] = sum[j++]; } if(i <= mid) while(i <= mid)                 temp[k++] = sum[i++]; else while(j <= r)                 temp[k++] = sum[j++]; for(i = 0; i < k; ++i)             sum[l++] = temp[i]; return count; } }; 

28 ms 12.2 MB