327.区间和的个数

链接：327.区间和的个数
难度：Hard
标签：树状数组、线段树、数组、二分查找、分治、有序集合、归并排序
简介：给定一个整数数组 nums，返回区间和在 [lower, upper] 之间的个数，包含 lower 和 upper。

题解 1 - typescript

• 编辑时间：2020-11-07
• 执行用时：280ms
• 内存消耗：40.4MB
• 编程语言：typescript
• 解法介绍：暴力法循环所有数，此题有多种解法,[参考链接](https://leetcode-cn.com/problems/count-of-range-sum/solution/qu-jian-he-de-ge-shu-by-leetcode-solution/)。

function countRangeSum(nums: number[], lower: number, upper: number): number {
  const len = nums.length;
  let c = 0;
  for (let i = 0; i < len; i++) {
    let sum = 0;
    for (let j = i; j < len; j++) {
      sum += nums[j];
      if (lower <= sum && sum <= upper) cpp;
    }
  }
  return c;
}

题解 2 - typescript

• 编辑时间：2021-05-14
• 执行用时：160ms
• 内存消耗：50.7MB
• 编程语言：typescript
• 解法介绍：分治，统计两部分中的符合结果的前缀和。

function countRangeSum(nums: number[], lower: number, upper: number): number {
  const len = nums.length;
  if (len === 0) return 0;
  const prefixSumList = [0];
  for (let i = 0; i < len; i++) prefixSumList[i + 1] = prefixSumList[i] + nums[i];
  const count = (left: number, mid: number, right: number) => {
    let i1 = left,
      i2 = left,
      ans = 0;
    for (let i = mid + 1; i <= right; i++) {
      const sum = prefixSumList[i];
      const l = sum - upper;
      const r = sum - lower;
      while (i1 <= mid && prefixSumList[i1] < l) i1++;
      while (i2 <= mid && prefixSumList[i2] <= r) i2++;
      ans += i2 - i1;
    }
    return ans;
  };
  const mergeSort = (left: number, right: number): number => {
    if (left === right) return 0;
    const mid = (left + right) >> 1;
    const ans = mergeSort(left, mid) + mergeSort(mid + 1, right) + count(left, mid, right);
    const temp = prefixSumList.slice(left, mid + 1);
    let p1 = 0,
      end1 = mid - left,
      p2 = mid + 1,
      i = left;
    while (p1 <= end1) {
      if (p2 > right || temp[p1] <= prefixSumList[p2]) prefixSumList[i++] = temp[p1++];
      else prefixSumList[i++] = prefixSumList[p2++];
    }
    return ans;
  };
  return mergeSort(0, len);
}