【一天一大 lee】区间和的个数 (难度:困难) - Day20201107

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

/**
 * @param {number[]} nums
 * @param {number} lower
 * @param {number} upper
 * @return {number}
 */
var countRangeSum = function(nums, lower, upper) {
 let _result = 0
 for (let i = 0; i < nums.length; i++) {
  // 区间和
  let item = 0
  for (let j = i; j < nums.length; j++) {
   item = item + nums[j]
   if (item >= lower && item <= upper) _result++
  }
 }
 return _result
};

var countRangeSum = function (nums, lower, upper) {
  // 前缀元素和
  let sum = [0] 
  for (let  i = 1;i <= nums.length;i++) {
    sum[i] = sum[i - 1] + nums[i - 1]
  }

  function helper (left, right) {
   if (left === right) return 0
    let mid = Math.floor((left + right) / 2),
        // 先递归切分区间
        result = helper(left, mid) + helper(mid + 1, right);

    // 统计left到right之前满足条件的下标组合数量
    let index = left,
        l = mid + 1,
        r = mid + 1;
    while (index <= mid) {
      while (l <= right && sum[l] - sum[index] < lower) l++;
      while (r <= right && sum[r] - sum[index] <= upper) r++;
      result += (r - l);
      index++;
    }

    // 两个合并子树形成一个有序数组，保证后续切分的数组均为有序数组
    let sorted = Array(right - left + 1),
        p1 = left, 
        p2 = mid + 1,
        p = 0;
    while (p1 <= mid || p2 <= right) {
      if (p1 > mid) {
        sorted[p++] = sum[p2++];
      } else if (p2 > right) {
        sorted[p++] = sum[p1++];
      } else {
        if (sum[p1] < sum[p2]) {
          sorted[p++] = sum[p1++];
        } else {
          sorted[p++] = sum[p2++];
        }
      }
    }
    for (let i = 0; i < sorted.length; i++) {
      sum[left + i] = sorted[i];
    }
    return result;
  }

  return helper(0, sum.length - 1);
};