2021 后端開發(fā)筆記 29 歸并排序（難）

今天總結(jié)的是一道非常難的算法題彼乌，leetcode第327題：區(qū)間和的個數(shù)（大家可以在這個鏈接上進(jìn)行測試）卸勺。同時想要理解這道題目需要非常理解歸并排序的流程赘方，所以希望大家先去看之前的歸并排序基礎(chǔ)（猛戳這個鏈接）的講解章咧，再來看這里厘托。

下面是leetcode官方的題目解釋：

評論說出題人的語文是體育老師教的

題目描述：

讓我來解釋一下這個題目羹幸，給定一個整數(shù)數(shù)組nums钙皮，和兩個整數(shù)lower和upper，返回nums中有多少個子數(shù)組的累加和在 [lower, upper] 的范圍上曼追。累加和是什么意思先解釋一下窍仰，根據(jù)例子[-2, 5, -1]，[0, 1]的累加和就是 $-2 + 5 = 3$ 礼殊， [0, 0]的累加和就是-2驹吮，[0, 2]的累積和就是 $-2 + 5 + （-1） = 2$ ，將數(shù)組中一個范圍上的數(shù)字累加起來就是累加和的含義晶伦。子數(shù)組必須是連續(xù)的碟狞，同時范圍是兩個閉區(qū)間，也就是左右兩個范圍都能取到婚陪，leetcode官方給的例子中的范圍是[-2, 2]族沃，也就是說在子數(shù)組和等于-2 和 2都算答案犀被。

根據(jù)leetcode給出的示例散址，在數(shù)組[-2 , 5, -1]上的子數(shù)組落在[ -2, 2]上面欣簇，首先leetcode所說的最直觀的解法就是暴力解法瘫镇，枚舉出所有的可能性，然后計算他們是否落在這個區(qū)間上盖溺，如果落在這個區(qū)間上就記錄下來漓糙。所以在這個實例中的答案有[0, 0] 也就是-2在這個區(qū)間上。[2, 2]也就是1也落在這個區(qū)間上烘嘱。[0, 2]就是說 $-2 + 5 + (-1) = 2$ 落在這個區(qū)間上昆禽。所以答案就是3個，返回3就對了蝇庭。

題目思路：

當(dāng)我們理解了題目之后为狸，我們先從暴力解開始講解，然后再過渡到優(yōu)化后的講解遗契。

暴力解：

假設(shè)我們有一個數(shù)組，長度為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 只剩一個驻债。然后將所有的累加和加起來，再進(jìn)行計算就是查看這些所有解是否落在我們的范圍上形葬，符合標(biāo)準(zhǔn)的就是我們的答案合呐。

image.png

我們能看出從0到9的累加和是一個等差數(shù)列，從總共9個到總共8個到總共7個笙以。淌实。。到最后總共只有一個，是一個差為1的等差數(shù)列（如上圖）翩伪。因此根據(jù)等差數(shù)列的求和公式 $S = An^2 + Bn$ 我們就能得到 $\frac{1}{2}*n^2 + a_1 *n + \frac{1}{2} * n$ 微猖，根據(jù)這個公式我們就能知道暴力解的枚舉所有可能性的時間復(fù)雜度是 $O(n^2)$ 的，同時因為他有一個 $O(n^2*log_2n)$ 的檢查過程缘屹。為什么檢查的過程是 $O(n^2*log_2n)$ 的復(fù)雜度呢凛剥？在長度為10的數(shù)組里，以0開始的累加和10個轻姿，然后長度是遞減的犁珠，所以這也是一個等差數(shù)列，這是也是一個 $O(n^2)$ 的復(fù)雜度互亮，然后從0犁享，以1開始，以2開始豹休，到以9開始的累加和數(shù)組的檢查的復(fù)雜度是依次下降的所以這是一個 $log_2n$ 的時間復(fù)雜度炊昆，所以實際上的時間復(fù)雜度是 $O(n^2 + n^2*log_2n)$ 的復(fù)雜度。然后再和舍去常數(shù)項我們就能得到 $O(n^2*log_2n)$ 的時間復(fù)雜度威根。

然后我們來看看如何優(yōu)化：

第一步優(yōu)化我們需要用到前綴和數(shù)組

首先我們來看看前綴和數(shù)組是什么：例如題目給的 $[-2,5,-1]$ 我們能轉(zhuǎn)換成前綴和數(shù)組 $[-2, 3, 2]$ 凤巨，我們可以看到前綴和數(shù)組的第一個位置是原數(shù)組0 到 0上面的累加和，1位置是0到1位置上面的累加和洛搀，2位置是0到2位置上面的累加和敢茁。

有前綴和數(shù)組的好處是什么？

原本在枚舉出所有可能性之后留美，如果我們需要計算出每個枚舉出來的數(shù)組我們還需要遍歷一遍每個枚舉出來的數(shù)組彰檬，計算結(jié)果是否達(dá)標(biāo)。但是現(xiàn)在如果我們想要算出0 到 1上面的累加和我們就直接訪問前綴和數(shù)組中下標(biāo)為1的元素就能找到谎砾，如果我們想知道 1 到 2 上面的累加和我們就直接用前綴和數(shù)組下標(biāo)為2上面的元素減去下標(biāo)為1上面的元素 $2 - (-2) = 4$ 逢倍，因此我們就知道原數(shù)組[1, 2]上面的累加和是4。這樣就省去了遍歷的過程景图，變成單純枚舉前綴和上的數(shù)組瓶堕，因此我們的復(fù)雜度就能優(yōu)化到 $O(n^2)$ 。

上面是第一步優(yōu)化症歇，接下來讓我們看看第二步優(yōu)化是什么：

第二部分的優(yōu)化我們是將 —— 枚舉前綴和數(shù)組郎笆，查看是否達(dá)標(biāo)在題目給定范圍上達(dá)標(biāo)，轉(zhuǎn)換成遍歷前綴和數(shù)組查看是否在達(dá)標(biāo)的問題Ｍ睢Ｍ痱尽！设塔！將一個原本 $O(n^2)$ 時間復(fù)雜度的過程轉(zhuǎn)換成 $O(n)$ 時間復(fù)雜度的過程凄吏。

從這個部分開始，接下來的內(nèi)容要求對歸并排序一定要有清晰的認(rèn)識，所以如果不懂歸并排序的請猛戳這個鏈接痕钢。

如何將枚舉過程轉(zhuǎn)換成遍歷過程图柏，先拋出結(jié)論，記不住沒關(guān)系任连，接下來會詳細(xì)解釋蚤吹，只要有個模糊概念就行了：

第一點(diǎn)： 以i位置結(jié)尾的子數(shù)組有多少個在[lower, upper]上滿足要求，也就等同于求i之前的所有前綴和數(shù)組中有多少前綴和在[ x - upper, x - lower]上随抠。

第二點(diǎn)：同時我們還需要使用到一個滑動窗口的技巧裁着，歸并排序在回溯階段，將每個分開的數(shù)字合并起來的階段合并的左右兩個數(shù)組是有序的拱她！也就是說這兩個數(shù)組是單調(diào)遞增的二驰，所以可以使用滑動窗口，不需要回退進(jìn)行檢查秉沼，只需要遍歷一遍數(shù)組就能完成檢索桶雀。

首先我們來講第一點(diǎn)是如何轉(zhuǎn)換的：

以i 位置結(jié)尾的子數(shù)組是什么意思？

假設(shè)我們有一個長度為15的數(shù)組0 -14范圍上的前綴和是100唬复，我們的目標(biāo)是[20, 60]背犯。以假設(shè) $i = 15$ ，我們就有 $0 - 15, 1 - 15, 2-15...直到15 -15范圍$ 如圖

image.png

如果我們想求 3 ~ 15上面的累加和是多少實際上就是15上面的累加和減去2上面的累加和盅抚，我們就能得到3 ~ 15的累加和。

如果我們想要計算7到15的累加和就是用15的累加和去減去6的累加和倔矾。

因此我們可以把前綴和范圍是否在目標(biāo)[20, 80]妄均，轉(zhuǎn)換成前綴和以15為結(jié)尾的前綴和是否在[100 - upper, 100 - lower] —— [100 - 80, 100 - 20] 上也就是是否在 [20, 80]上！Ｄ淖浴丰包！所以我們得到了我們的新目標(biāo)[20, 80]

假設(shè) 2位置上的前綴和是10，那么如果計算3 到 15的前綴和是否達(dá)標(biāo)就是計算3到15的累加和減去2位置上的累加和 $100 - 10 = 90$ 就在不在目標(biāo)[20, 80]上壤巷，顯然是不在的邑彪。

假設(shè)0 到 6的前綴和是30，這個數(shù)字是在我們的新目標(biāo)[20, 80]上的胧华。那么7 到 15的前綴和就是 100 - 30 = 70 就在我們的真實目標(biāo)[80, 20]上面寄症。

因此我們就能將以i位置結(jié)尾的子數(shù)組有多少個在[lower, upper]上滿足要求，轉(zhuǎn)換成求i之前的所有前綴和數(shù)組中有多少前綴和在[ x - upper, x - lower]上矩动。

現(xiàn)在我們來講第二點(diǎn)：如何利用歸并排序回溯過程中的單調(diào)性有巧，進(jìn)行滑動窗口檢索

在歸并排序回溯合并數(shù)組的時候是兩兩為一組的，所以我們假設(shè)現(xiàn)在有左組 $[ 3, 5, 7, 8]$ 右組 $[4, 7, 10, 12]$ 我們的目標(biāo)是 $[1, 4]$ 悲没。

如果我們要查看以4位結(jié)尾的前綴和數(shù)組是否在目標(biāo) $[1, 4]$ 上篮迎，我們就需要首先計算以4為結(jié)尾的新目標(biāo)——[4 - 4, 4 - 1]也就是 $[0, 3]$ 。

同時我們設(shè)置兩個指針左指針 L 和右指針R。指針包含的范圍是 $[L , R)$ 甜橱，也就是說逊笆，如果指針L在0，R在1只包括0位置上面的數(shù)字不包括1上面的數(shù)字岂傲。

一開始我們的數(shù)組是這樣的难裆，左右指針指向0位置，這時候其實滑動窗口內(nèi)是沒有任何數(shù)字的譬胎，右組上的第一個數(shù)字會產(chǎn)生新目標(biāo)[0, 3]差牛，所以我們首先讓右指針查看是否符合新目標(biāo)，因此R指針會移動到5上面堰乔。因此這時候右指針已經(jīng)不符合我們的目標(biāo)了偏化，同時因為歸并的每個組都是有序的，所以接下來的都是不符合的镐侯。然后我們檢查左指針侦讨，他是大于等于新目標(biāo)的最小值的。所以我們不需要移動左指針L苟翻。因此我們就得到了答案下標(biāo)1 - 下標(biāo)0韵卤， $1 - 0 = 1$ 因此我們符合目標(biāo)的答案+1。

image.png

因為左組中的右指針已經(jīng)不符合了崇猫，所以我們移動右組的目標(biāo)到下一個沈条。這時候我們來到了右組的7，我們計算新的目標(biāo) $[3, 6]$ 诅炉。然后移動右指針R到大于6的情況蜡歹。然后檢查左指針L是否大于等于3。然后我們再用右指針R - 左指針L涕烧，我們就能得到 $2 - 0 = 2$ 月而，因此符合目標(biāo)情況的數(shù)字增加兩個。剩下的以此類推议纯，大家可以自己畫一畫父款。

image.png

同時解釋一下為什么右組中的數(shù)也可以不回退的檢查，也是因為歸并排序的右組也是單調(diào)遞增的瞻凤，所以只要往右移當(dāng)前新目標(biāo)一定比前一個新目標(biāo)大憨攒，上面第一個例子[0, 3]的范圍一定沒有[3,6]的范圍大。

最后再解釋一下為什么能夠?qū)⑺械那闆r都檢查到阀参，不遺漏任何一種情況浓恶，如圖歸并排序遞歸到最后一定會將所有元素分解成最小情況，同時遞歸的過程必然是深度優(yōu)先的结笨。滑動窗口是從左到右的包晰，因此以1位置為結(jié)尾的前綴和一定會減去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) {
        // 主函數(shù)用來調(diào)用遞歸杉樹
        if (nums == null || nums.length == 0) { // 數(shù)組邊界條件判斷
            return 0;
        }
        long[] sum = new long[nums.length]; // 前綴和數(shù)組生成
        sum[0] = nums[0]; // 先處理第一個前綴和
        for (int i = 1; i < nums.length; i++) { // 剩下的前綴和就是當(dāng)前數(shù)字加上前面后一個數(shù)字
            sum[i] = sum[i - 1] + nums[i];
        }
        // 調(diào)用遞歸函數(shù)
        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) { // 當(dāng)我們遞歸到最小子問題的時候 也就是 0到0的情況0到1的情況沒有進(jìn)行判斷雏掠，統(tǒng)一在這進(jìn)行處理
            return sum[L] >= lower && sum[L] <= upper ? 1 : 0;
        }
        int M = L + ((R - L) >> 1); // 設(shè)置范圍
        return process(sum, L, M, lower, upper) + process(sum, M + 1, R, lower, upper)
                + merge(sum, L, M, R, lower, upper); // 將左邊結(jié)果和右邊結(jié)果加到一起
    }

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

        int ans = 0; // 用來存儲結(jié)果的數(shù)量
        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++; // 每當(dāng)遍歷一個右組的元素的時候查看左組是否有符合條件的
            }
            while (windowL <= M && arr[windowL] < min) {
                windowL++;
            }
            ans += windowR - windowL;// 記錄結(jié)果
        }
        
        // 歸并合并左右組
        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;
    }

代碼大家可以在這個鏈接上進(jìn)行檢查

最后非常感謝左神，因為剛開始學(xué)習(xí)算法理解這個比較困難劣像，跟左神交流了一下乡话，晚上語音通話和我單獨(dú)講了一遍。

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