[路飞]_leetcode-327-区间和的个数

[题目地址][B站地址]

给你一个整数数组 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 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• -105 <= lower <= upper <= 105
• 题目数据保证答案是一个 32 位 的整数

前缀和数组

所谓前缀和数组，就是数组中的每一项，等于原数组中当前位置及之前元素的和值。

例如原数组为 [1,2,3,4], 前缀和数组为 [0,1,3,6,10]。 要注意的是前缀和数组中默认第一位是 0,所以前缀和数组的长度会比原数组长度 +1。

为什么要有一个前置 0呢？

1. 方便计算前缀和数组的第一项的值。因为我们求前缀和数组中当前项值的时候，只需要将前一项的值加上原数组前位置的元素值即可，那么为了原数组第一个元素计算的时候有前一项值，所以需要一个前置 0。
2. 方便计算区间和值。观察前缀和数组可以发现，后面的值减去前面的值，刚好等于原数组中该区间中的元素和值，即区间和值。那每一项减去最前面的 0,其实就是从原数组下标 0到当前位置的区间和值（这里要注意的是，因为有一个前置 0，所以前缀和数组中的下标等于原数组中的下标 +1）。

解题思路

涉及到求区间和的问题，我们可以尝试使用前缀和数组来解题。

这里我们首先求得原数组的前缀和数组，拿到前缀和数组有什么用呢？我们接着往下看。

接下来，我们对前缀和数组进行 归并排序。

假设此时我们来到了归并排序的回溯过程，此时左区间有序且右区间有序。并且左区间的值的下标都小于右区间的值的下标。

又因为前缀和数组中，后面的值减去前面的值等于原数组中该区间的元素和值，也就是区间和值。所以此时如果右区间的某个元素减去左区间的某个元素，差值刚好在给定的 lower~upper 之间，则说明找到了一个符合要求的区间和值。

假设右侧区间元素的下标为 j,左侧区间元素的下标为 i,则应该有 sums[j]-sums[i]>=lower 并且 sums[j]-sums[i]<=upper 。从而得到 sums[i]<=sums[j]-lower 并且 sums[i]>=sums[j]-upper。 将 sums[j]-lower 记作 max,sums[j]-upper 记作 min,则左区间中所有满足 min<=sums[i]<=max 的元素，都可以和右区间中当前的 sums[j] 组成符合要求的区间和。

又因为左区间有序，所以找到一个起始位置 sums[start]>=min 和一个结束位置 sums[end]<=max,则该区间中的所有元素都可以都可以和右区间中当前的 sums[j] 组成符合要求的区间和。

又因为右区间也是有序的，所以右区间的下一个元素对应的 min 和 max 肯定大于等于之前的 min和max，所以我们可以记忆上一次查找的区间位置，在之前基础上继续查找，这样就实现了查找加速。

动画演示

代码实现

var countRangeSum = function(nums, lower, upper) {
  // 初始化前缀和数组
  const sums = [0]
  // 获取前缀和数组
  for(let i = 0;i<nums.length;i++){
    sums[i+1] = sums[i]+nums[i]
  }
  // 初始化结果值
  let num = 0;
  // 获取前缀和数组长度并初始化归并排序暂存数组
  const len = sums.length,temp = Array(len);
  // 归并排序
  function mergeSort(l,r){
    // 如果区间中元素小于两个，直接返回
    if(l>=r) return;
    // 获取当前区间中间下标
    const mid = (l+r)>>1;
    // 递归处理左区间
    mergeSort(l,mid)
    // 递归处理右区间
    mergeSort(mid+1,r);
    // 初始化满足条件的起始位置和结束位置
    let start = l,end = l;
    // 遍历右区间的元素
    for(let j = mid+1;j<=r;j++){
      // 计算左区间中满足条件的匹配项的最大最小值
      const min = sums[j]-upper,
      max = sums[j]-lower;
      // 获取做区间中满足条件的匹配项的开始下标
      while(sums[start]<min&&start<=mid) start++
      // 获取做区间中满足条件的匹配项的结束下标
      while(sums[end]<=max&&end<=mid) end++
      // 计算满足条件元素的数量，并累加到结果值
      num += end-start
    }
    // 回溯过程合并左右有序区间
    let k = l,p1 = l,p2 = mid+1;
    while(p1<=mid || p2<=r){
      if(p2>r || (p1<=mid&&sums[p1]<=sums[p2])){
        temp[k++] = sums[p1++]
      }else{
        temp[k++] = sums[p2++]
      }
    }
    for(let i = l;i<=r;i++) sums[i] = temp[i]
  }
  mergeSort(0,len-1)
  // 返回结果
  return num;
};
复制代码

至此我们就完成了 leetcode-327-区间和的个数

如有任何问题或建议，欢迎留言讨论！