【算法100天 | 14】归并排序系列问题2：区间和的个数（LeetCode 327）

水深无声 2023-09-24 13:09 124阅读 0赞

#### 文章目录 ####

*   *  1、LeetCode 327. 区间和的个数（难度：困难）
     *  方法一：暴力法
     *   *  思路
     *  方法二：归并排序
     *   *  1）思路
         *  2）代码
     *  其他方法

### 1、LeetCode 327. 区间和的个数（难度：困难） ###

给你一个整数数组 `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 位 的整数

### 方法一：暴力法 ###

#### 思路 ####

题目要求数组的某个子数组的区间和在\[lower, upper\]范围，求出这样子数组的个数；

暴力业务思想：针对数组中的每一个数，都以其为起点，遍历数组中后续的数 进行累加操作，判断累加和是否在\[lower, upper\]范围；

*  如果再，则结果 + 1。
 *  否则，停止遍历，进入最外层循环的下一轮。

### 方法二：归并排序 ###

#### 1）思路 ####

假设 0 - i 上整体的累加和为x，题目要求的累加和范围为\[lower, upper\]；

求必须以 i 位置结尾的子数组，有个多少个子数组的累加和在\[lower, upper\]范围上，等价于求 i 之前的所有前缀和中，有多少前缀和 在 \[x- upper, x - lower\]范围。

针对前缀和数组做归并排序的过程中：

*  对于任何一个右序列中的数，只需求左序列中有多少个数符合要求；有多少个数，则结果累加 几。
 *  但是再归并排序merge的过程 右序列无法知道自身是否满足条件，所以需要在拆分的一层判断0-left的前缀和是否在\[lower,upper\]之间，在则结果累加 1。

#### 2）代码 ####

/**
     * 假设 0 - i 上整体的累加和为x，题目要求的累加和范围为[lower, upper]
     * 求必须以 i 位置结尾的子数组，有个多少个子数组的累加和在[lower, upper]范围上，等价于求 i 之前的所有前缀和中，有多少前缀和 在 [x- upper, x - lower]范围
     */
    public int countRangeSum(int[] nums, int lower, int upper) {
        
        if (nums == null || nums.length < 1) {
        
            return 0;
        }
        int n = nums.length;
        long[] preSums = new long[n];
        preSums[0] = nums[0];
        for (int i = 1; i < n; i++) {
        
            preSums[i] = nums[i] + preSums[i - 1];
        }
        // 辅助数组
        long[] temp = new long[n];
        return count(preSums, 0, n - 1, lower, upper, temp);
    }
    
    /**
     * @param preSums 前缀和数组
     */
    private static int count(long[] preSums, int left, int right, int lower, int upper, long[] temp) {
        
    
        // 0-left的前缀和在[lower,upper]之间，则返回1
        if (left == right) {
        
            return preSums[left] >= lower && preSums[left] <= upper ? 1 : 0;
        }
        int mid = left + ((right - left) >> 1);
    
        return count(preSums, left, mid, lower, upper, temp)
                + count(preSums, mid + 1, right, lower, upper, temp)
                + merge(preSums, left, mid, right, lower, upper, temp);
    }
    
    /**
     * 任何一个右序列中的数，左序列中有多少个数符合要求；
     * 但是这里右序列无法知道自身是否满足条件，所以要在上层做一个特殊处理
     *
     * @param preSums 前缀和数组
     */
    private static int merge(long[] preSums, int left, int mid, int right, int lower, int upper, long[] temp) {
        
    
        int res = 0;
        int windowL = left;
        int windowR;
        // [windowL, windowR)，窗口的结果是左闭右开的。由于左右序列分别有序，所以windowL、windowR不需要回溯
        for (int i = mid + 1; i <= right; i++) {
        
            long min = preSums[i] - upper;
            long max = preSums[i] - lower;
            while (windowL <= mid && preSums[windowL] < min) {
        
                windowL++;
            }
            windowR = windowL;
            while (windowR <= mid && preSums[windowR] <= max) {
        
                windowR++;
            }
            res += windowR - windowL;
        }
    
        int pLeft = left;
        int pRight = mid + 1;
        int t = 0;
        while (pLeft <= mid && pRight <= right) {
        
            temp[t++] = preSums[pLeft] <= preSums[pRight] ? preSums[pLeft++] : preSums[pRight++];
        }
        while (pLeft <= mid) {
        
            temp[t++] = preSums[pLeft++];
        }
        while (pRight <= right) {
        
            temp[t++] = preSums[pRight++];
        }
    
        t = 0;
        while (left <= right) {
        
            preSums[left++] = temp[t++];
        }
        return res;
    }

**测试结果：**

![在这里插入图片描述][05139bf6793147fa85a6ae5da460a7d0.png]

### 其他方法 ###

由于本篇专注于归并排序系列问题，所以暂时不提供其他解法。

[05139bf6793147fa85a6ae5da460a7d0.png]: https://img-blog.csdnimg.cn/05139bf6793147fa85a6ae5da460a7d0.png