题目

题目来源：力扣（LeetCode）

给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

示例 1：
输入：nums = [-2,5,-1], lower = -2, upper = 2
输出：3
解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。

示例 2：

输入：nums = [0], lower = 0, upper = 0
输出：1

思路分析

归并排序

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} lower
  4.  * @param {number} upper
  5.  * @return {number}
  6.  */
  7. const countRangeSumRecursive = (sum, lower, upper, left, right) => {
  8.     if (left === right) {
  9.         return 0;
  10.     } else {
  11.         const mid = Math.floor((left + right) / 2);
  12.         const n1 = countRangeSumRecursive(sum, lower, upper, left, mid);
  13.         const n2 = countRangeSumRecursive(sum, lower, upper, mid + 1, right);
  14.         let ret = n1 + n2;
  16.         // 首先统计下标对的数量
  17.         let i = left;
  18.         let l = mid + 1;
  19.         let r = mid + 1;
  20.         while (i <= mid) {
  21.             while (l <= right && sum[l] - sum[i] < lower) l++;
  22.             while (r <= right && sum[r] - sum[i] <= upper) r++;
  23.             ret += (r - l);
  24.             i++;
  25.         }
  27.         // 随后合并两个排序数组
  28.         const sorted = new Array(right - left + 1);
  29.         let p1 = left, p2 = mid + 1;
  30.         let p = 0;
  31.         while (p1 <= mid || p2 <= right) {
  32.             if (p1 > mid) {
  33.                 sorted[p++] = sum[p2++];
  34.             } else if (p2 > right) {
  35.                 sorted[p++] = sum[p1++];
  36.             } else {
  37.                 if (sum[p1] < sum[p2]) {
  38.                     sorted[p++] = sum[p1++];
  39.                 } else {
  40.                     sorted[p++] = sum[p2++];
  41.                 }
  42.             }
  43.         }
  44.         for (let i = 0; i < sorted.length; i++) {
  45.             sum[left + i] = sorted[i];
  46.         }
  47.         return ret;
  48.     }
  49. }
  50. var countRangeSum = function(nums, lower, upper) {
  51.     let s = 0;
  52.     const sum = [0];
  53.     for(const v of nums) {
  54.         s += v;
  55.         sum.push(s);
  56.     }
  57.     return countRangeSumRecursive(sum, lower, upper, 0, sum.length - 1);
  58. };