一個小而美的算法技巧：差分數(shù)組

本文給大家介紹一個小而美的算法技巧：差分數(shù)組。

讀完本文，你可以去解決力扣第 1109 題「航班預訂統(tǒng)計」，難度Medium

差分數(shù)組技巧是前文前綴和技巧詳解寫過的前綴和技巧的兄弟。

前綴和主要適用的場景是原始數(shù)組不會被修改的情況下，頻繁查詢某個區(qū)間的累加和。

沒看過前文沒關(guān)系，這里簡單介紹一下前綴和，核心代碼就是下面這段：

classPrefixSum{ //前綴和數(shù)組 privateint[]prefix; /*輸入一個數(shù)組，構(gòu)造前綴和*/ publicPrefixSum(int[]nums){ prefix=newint[nums.length+1]; //計算nums的累加和 for(inti=1;i

prefix[i]就代表著nums[0..i-1]所有元素的累加和，如果我們想求區(qū)間nums[i..j]的累加和，只要計算prefix[j+1] - prefix[i]即可，而不需要遍歷整個區(qū)間求和。

本文講一個和前綴和思想非常類似的算法技巧「差分數(shù)組」，差分數(shù)組的主要適用場景是頻繁對原始數(shù)組的某個區(qū)間的元素進行增減。

比如說，我給你輸入一個數(shù)組nums，然后又要求給區(qū)間nums[2..6]全部加 1，再給nums[3..9]全部減 3，再給nums[0..4]全部加 2，再給…

一通操作猛如虎，然后問你，最后nums數(shù)組的值是什么？

常規(guī)的思路很容易，你讓我給區(qū)間nums[i..j]加上val，那我就一個 for 循環(huán)給它們都加上唄，還能咋樣？這種思路的時間復雜度是 O(N)，由于這個場景下對nums的修改非常頻繁，所以效率會很低下。

這里就需要差分數(shù)組的技巧，類似前綴和技巧構(gòu)造的prefix數(shù)組，我們先對nums數(shù)組構(gòu)造一個diff差分數(shù)組，diff[i]就是nums[i]和nums[i-1]之差：

int[]diff=newint[nums.length]; //構(gòu)造差分數(shù)組 diff[0]=nums[0]; for(inti=1;i

通過這個diff差分數(shù)組是可以反推出原始數(shù)組nums的，代碼邏輯如下：

int[]res=newint[diff.length]; //根據(jù)差分數(shù)組構(gòu)造結(jié)果數(shù)組 res[0]=diff[0]; for(inti=1;i

這樣構(gòu)造差分數(shù)組diff，就可以快速進行區(qū)間增減的操作，如果你想對區(qū)間nums[i..j]的元素全部加 3，那么只需要讓diff[i] += 3，然后再讓diff[j+1] -= 3即可：

原理很簡單，回想diff數(shù)組反推nums數(shù)組的過程，diff[i] += 3意味著給nums[i..]所有的元素都加了 3，然后diff[j+1] -= 3又意味著對于nums[j+1..]所有元素再減 3，那綜合起來，是不是就是對nums[i..j]中的所有元素都加 3 了？

只要花費 O(1) 的時間修改diff數(shù)組，就相當于給nums的整個區(qū)間做了修改。多次修改diff，然后通過diff數(shù)組反推，即可得到nums修改后的結(jié)果。

現(xiàn)在我們把差分數(shù)組抽象成一個類，包含increment方法和result方法：

classDifference{ //差分數(shù)組 privateint[]diff; publicDifference(int[]nums){ assertnums.length>0; diff=newint[nums.length]; //構(gòu)造差分數(shù)組 diff[0]=nums[0]; for(inti=1;i

這里注意一下increment方法中的 if 語句：

publicvoidincrement(inti,intj,intval){ diff[i]+=val; if(j+1

當j+1 >= diff.length時，說明是對nums[i]及以后的整個數(shù)組都進行修改，那么就不需要再給diff數(shù)組減val了。

算法實踐

這里看一下力扣第 1109 題「航班預訂統(tǒng)計」：

函數(shù)簽名如下：

int[]corpFlightBookings(int[][]bookings,intn)

這個題目就在那繞彎彎，其實它就是個差分數(shù)組的題，我給你翻譯一下：

給你輸入一個長度為n的數(shù)組nums，其中所有元素都是 0。再給你輸入一個bookings，里面是若干三元組(i,j,k)，每個三元組的含義就是要求你給nums數(shù)組的閉區(qū)間[i-1,j-1]中所有元素都加上k。請你返回最后的nums數(shù)組是多少？

PS：因為題目說的n是從 1 開始計數(shù)的，而數(shù)組索引從 0 開始，所以對于輸入的三元組(i,j,k)，數(shù)組區(qū)間應該對應[i-1,j-1]。

這么一看，不就是一道標準的差分數(shù)組題嘛？我們可以直接復用剛才寫的類：

int[]corpFlightBookings(int[][]bookings,intn){ //nums初始化為全0 int[]nums=newint[n]; //構(gòu)造差分解法 Differencedf=newDifference(nums); for(int[]booking:bookings){ //注意轉(zhuǎn)成數(shù)組索引要減一哦 inti=booking[0]-1; intj=booking[1]-1; intval=booking[2]; //對區(qū)間nums[i..j]增加val df.increment(i,j,val); } //返回最終的結(jié)果數(shù)組 returndf.result(); }

這道題就解決了。

其實我覺得差分數(shù)組和前綴和數(shù)組都是比較常見且巧妙的算法技巧，分別適用不同的常見，而且是會者不難，難者不會。所以，關(guān)于差分數(shù)組的使用，你學會了嗎？！