2021 后端开发笔记 29 归并排序（难）

今天总结的是一道非常难的算法题，leetcode第327题：区间和的个数（大家可以在这个链接上进行测试）。同时想要理解这道题目需要非常理解归并排序的流程，所以希望大家先去看之前的归并排序基础（猛戳这个链接）的讲解，再来看这里。

下面是leetcode官方的题目解释：

评论说出题人的语文是体育老师教的

题目描述：

让我来解释一下这个题目，给定一个整数数组nums，和两个整数lower和upper，返回nums中有多少个子数组的累加和在 [lower, upper] 的范围上。累加和是什么意思先解释一下，根据例子[-2, 5, -1]，[0, 1]的累加和就是 $-2 + 5 = 3$ ， [0, 0]的累加和就是-2，[0, 2]的累积和就是 $-2 + 5 + （-1） = 2$ ，将数组中一个范围上的数字累加起来就是累加和的含义。子数组必须是连续的，同时范围是两个闭区间，也就是左右两个范围都能取到，leetcode官方给的例子中的范围是[-2, 2]，也就是说在子数组和等于-2 和 2都算答案。

根据leetcode给出的示例，在数组[-2 , 5, -1]上的子数组落在[ -2, 2]上面，首先leetcode所说的最直观的解法就是暴力解法，枚举出所有的可能性，然后计算他们是否落在这个区间上，如果落在这个区间上就记录下来。所以在这个实例中的答案有[0, 0] 也就是-2在这个区间上。[2, 2]也就是1也落在这个区间上。[0, 2]就是说 $-2 + 5 + (-1) = 2$ 落在这个区间上。所以答案就是3个，返回3就对了。

题目思路：

当我们理解了题目之后，我们先从暴力解开始讲解，然后再过渡到优化后的讲解。

暴力解：

假设我们有一个数组，长度为10，我们枚举出所有的可能性就是：0到0的累加和，0到1的累加和， 0到2的累加和，0到3的累加和一直到 0 到 9 的累加和，一共是10个（如下图）。从1开始就是：1 到 1的累加和 1 到 2的累加和一直到1 到 9的累加和，一共是9个，剩下的以此类推，从2开始的就是8个，后面 7个 6个 5个。。。。。。直到最后一个9 到 9 只剩一个。然后将所有的累加和加起来，再进行计算就是查看这些所有解是否落在我们的范围上，符合标准的就是我们的答案。

image.png

我们能看出从0到9的累加和是一个等差数列，从总共9个到总共8个到总共7个。。。到最后总共只有一个，是一个差为1的等差数列（如上图）。因此根据等差数列的求和公式 $S = An^2 + Bn$ 我们就能得到 $\frac{1}{2}*n^2 + a_1 *n + \frac{1}{2} * n$ ，根据这个公式我们就能知道暴力解的枚举所有可能性的时间复杂度是 $O(n^2)$ 的，同时因为他有一个 $O(n^2*log_2n)$ 的检查过程。为什么检查的过程是 $O(n^2*log_2n)$ 的复杂度呢？在长度为10的数组里，以0开始的累加和10个，然后长度是递减的，所以这也是一个等差数列，这是也是一个 $O(n^2)$ 的复杂度，然后从0，以1开始，以2开始，到以9开始的累加和数组的检查的复杂度是依次下降的所以这是一个 $log_2n$ 的时间复杂度，所以实际上的时间复杂度是 $O(n^2 + n^2*log_2n)$ 的复杂度。然后再和舍去常数项我们就能得到 $O(n^2*log_2n)$ 的时间复杂度。

然后我们来看看如何优化：

第一步优化我们需要用到前缀和数组

首先我们来看看前缀和数组是什么：例如题目给的 $[-2,5,-1]$ 我们能转换成前缀和数组 $[-2, 3, 2]$ ，我们可以看到前缀和数组的第一个位置是原数组0 到 0上面的累加和，1位置是0到1位置上面的累加和，2位置是0到2位置上面的累加和。

有前缀和数组的好处是什么？

原本在枚举出所有可能性之后，如果我们需要计算出每个枚举出来的数组我们还需要遍历一遍每个枚举出来的数组，计算结果是否达标。但是现在如果我们想要算出0 到 1上面的累加和我们就直接访问前缀和数组中下标为1的元素就能找到，如果我们想知道 1 到 2 上面的累加和我们就直接用前缀和数组下标为2上面的元素减去下标为1上面的元素 $2 - (-2) = 4$ ，因此我们就知道原数组[1, 2]上面的累加和是4。这样就省去了遍历的过程，变成单纯枚举前缀和上的数组，因此我们的复杂度就能优化到 $O(n^2)$ 。

上面是第一步优化，接下来让我们看看第二步优化是什么：

第二部分的优化我们是将 —— 枚举前缀和数组，查看是否达标在题目给定范围上达标，转换成遍历前缀和数组查看是否在达标的问题！！！！将一个原本 $O(n^2)$ 时间复杂度的过程转换成 $O(n)$ 时间复杂度的过程。

从这个部分开始，接下来的内容要求对归并排序一定要有清晰的认识，所以如果不懂归并排序的请猛戳这个链接。

如何将枚举过程转换成遍历过程，先抛出结论，记不住没关系，接下来会详细解释，只要有个模糊概念就行了：

第一点： 以i位置结尾的子数组有多少个在[lower, upper]上满足要求，也就等同于求i之前的所有前缀和数组中有多少前缀和在[ x - upper, x - lower]上。

第二点：同时我们还需要使用到一个滑动窗口的技巧，归并排序在回溯阶段，将每个分开的数字合并起来的阶段合并的左右两个数组是有序的！也就是说这两个数组是单调递增的，所以可以使用滑动窗口，不需要回退进行检查，只需要遍历一遍数组就能完成检索。

首先我们来讲第一点是如何转换的：

以i 位置结尾的子数组是什么意思？

假设我们有一个长度为15的数组0 -14范围上的前缀和是100，我们的目标是[20, 60]。以假设 $i = 15$ ，我们就有 $0 - 15, 1 - 15, 2-15...直到15 -15范围$ 如图

image.png

如果我们想求 3 ~ 15上面的累加和是多少实际上就是15上面的累加和减去2上面的累加和，我们就能得到3 ~ 15的累加和。

如果我们想要计算7到15的累加和就是用15的累加和去减去6的累加和。

因此我们可以把前缀和范围是否在目标[20, 80]，转换成前缀和以15为结尾的前缀和是否在[100 - upper, 100 - lower] —— [100 - 80, 100 - 20] 上也就是是否在 [20, 80]上！！！所以我们得到了我们的新目标[20, 80]

假设 2位置上的前缀和是10，那么如果计算3 到 15的前缀和是否达标就是计算3到15的累加和减去2位置上的累加和 $100 - 10 = 90$ 就在不在目标[20, 80]上，显然是不在的。

假设0 到 6的前缀和是30，这个数字是在我们的新目标[20, 80]上的。那么7 到 15的前缀和就是 100 - 30 = 70 就在我们的真实目标[80, 20]上面。

因此我们就能将以i位置结尾的子数组有多少个在[lower, upper]上满足要求，转换成求i之前的所有前缀和数组中有多少前缀和在[ x - upper, x - lower]上。

现在我们来讲第二点：如何利用归并排序回溯过程中的单调性，进行滑动窗口检索

在归并排序回溯合并数组的时候是两两为一组的，所以我们假设现在有左组 $[ 3, 5, 7, 8]$ 右组 $[4, 7, 10, 12]$ 我们的目标是 $[1, 4]$ 。

如果我们要查看以4位结尾的前缀和数组是否在目标 $[1, 4]$ 上，我们就需要首先计算以4为结尾的新目标——[4 - 4, 4 - 1]也就是 $[0, 3]$ 。

同时我们设置两个指针左指针 L 和右指针R。指针包含的范围是 $[L , R)$ ，也就是说，如果指针L在0，R在1只包括0位置上面的数字不包括1上面的数字。

一开始我们的数组是这样的，左右指针指向0位置，这时候其实滑动窗口内是没有任何数字的，右组上的第一个数字会产生新目标[0, 3]，所以我们首先让右指针查看是否符合新目标，因此R指针会移动到5上面。因此这时候右指针已经不符合我们的目标了，同时因为归并的每个组都是有序的，所以接下来的都是不符合的。然后我们检查左指针，他是大于等于新目标的最小值的。所以我们不需要移动左指针L。因此我们就得到了答案下标1 - 下标0， $1 - 0 = 1$ 因此我们符合目标的答案+1。

image.png

因为左组中的右指针已经不符合了，所以我们移动右组的目标到下一个。这时候我们来到了右组的7，我们计算新的目标 $[3, 6]$ 。然后移动右指针R到大于6的情况。然后检查左指针L是否大于等于3。然后我们再用右指针R - 左指针L，我们就能得到 $2 - 0 = 2$ ，因此符合目标情况的数字增加两个。剩下的以此类推，大家可以自己画一画。

image.png

同时解释一下为什么右组中的数也可以不回退的检查，也是因为归并排序的右组也是单调递增的，所以只要往右移当前新目标一定比前一个新目标大，上面第一个例子[0, 3]的范围一定没有[3,6]的范围大。

最后再解释一下为什么能够将所有的情况都检查到，不遗漏任何一种情况，如图归并排序递归到最后一定会将所有元素分解成最小情况，同时递归的过程必然是深度优先的。滑动窗口是从左到右的，因此以1位置为结尾的前缀和一定会减去0位置上的前缀和，查看1 到1位置上的情况是否符合，三位置的一定会减去2位置的前缀和查看3 到 3位置的前缀和是否符合情况，这就是红圈中剪头表示的意义。

然后如果往上一层，左组是[0, 1]，右组是[2, 3]，所以右组的3必然会检查1 到3 的情况和2到3的情况，因此所有的情况都检查到了。

image.png

接下来是代码讲解：

public static int countRangeSum(int[] nums, int lower, int upper) {
        // 主函数用来调用递归杉树
        if (nums == null || nums.length == 0) { // 数组边界条件判断
            return 0;
        }
        long[] sum = new long[nums.length]; // 前缀和数组生成
        sum[0] = nums[0]; // 先处理第一个前缀和
        for (int i = 1; i < nums.length; i++) { // 剩下的前缀和就是当前数字加上前面后一个数字
            sum[i] = sum[i - 1] + nums[i];
        }
        // 调用递归函数
        return process(sum, 0, sum.length - 1, lower, upper);
    }

    public static int process(long[] sum, int L, int R, int lower, int upper) {
        if (L == R) { // 当我们递归到最小子问题的时候 也就是 0到0的情况0到1的情况没有进行判断，统一在这进行处理
            return sum[L] >= lower && sum[L] <= upper ? 1 : 0;
        }
        int M = L + ((R - L) >> 1); // 设置范围
        return process(sum, L, M, lower, upper) + process(sum, M + 1, R, lower, upper)
                + merge(sum, L, M, R, lower, upper); // 将左边结果和右边结果加到一起
    }

    public static int merge(long[] arr, int L, int M, int R, int lower, int upper) {

        int ans = 0; // 用来存储结果的数量
        int windowL = L; // 窗口左指针
        int windowR = L; // 窗口右指针
        // [windowL, windowR)
        for (int i = M + 1; i <= R; i++) { // 右组
            long min = arr[i] - upper;
            long max = arr[i] - lower;
            while (windowR <= M && arr[windowR] <= max) {
                windowR++; // 每当遍历一个右组的元素的时候查看左组是否有符合条件的
            }
            while (windowL <= M && arr[windowL] < min) {
                windowL++;
            }
            ans += windowR - windowL;// 记录结果
        }
        
        // 归并合并左右组
        long[] help = new long[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = M + 1;
        while (p1 <= M && p2 <= R) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= M) {
            help[i++] = arr[p1++];
        }
        while (p2 <= R) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
        return ans;
    }

代码大家可以在这个链接上进行检查

最后非常感谢左神，因为刚开始学习算法理解这个比较困难，跟左神交流了一下，晚上语音通话和我单独讲了一遍。

Reference：https://italk.mashibing.com/course/detail/cour_00004003