差分數組入門
差分數組
什麼是差分數組？
差分數組：差分數組就是原始數組相鄰元素之間的差。
其實差分數組是一個輔助數組，從側面來表示給定某一數組的變化，一般用來對數組進行區間修改的操作。
比如說對於上文的數組，將區間【1，4】的數值全部加上3，其實當原始數組中元素同時加上或者減掉某個數，那麼他們的差分數組其實是不會變化的，如下圖所示：
對區間 [1, 4] 的元素都進行加3操作，差分數組中改變的只是 d[1] 和 d[5]，而 d[2] d[3] d[4] 都沒變。
把上一步得到的數組當成原數組，再將區間【3，5】的數值全部減去5，結果如下：
總結：當對一數組的某個區間進行增減某個值時，其差分數組對應的區間左端點的值會同步變化，而他的右端點的後一個值則會相反變化。
參考博文：差分數組
差分數組的作用
差分數組的作用就是求多次進行區間修改後的數組。構造出差分數組，就可以快速進行區間增減了。花費O(1)的時間修改 diff 數組，就相當於給原數組的整個區間做了修改。
注意 ：只能是區間元素同時增加或減少相同的數的情況才能用。
編碼實現
通過原數組求出差分數組：
int[] diff = new int[nums.length];
// 根據原數組構造差分數組
diff[0] = nums[0];
for(int i = 1; i < nums.length; ++i) {
diff[i] = nums[i] - nums[i - 1];
}
通過差分數組得到結果數組：
int[] res = new int[diff.length];
// 通過差分數組得到結果數組
res[0] = diff[0];
for(int i = 1; i < diff.length; ++i) {
res[i] = res[i - 1] + diff[i];
}
return res;
//-------------其實直接在diff上操作即可得到結果數組----------------
for(int i = 1; i < diff.length; ++i) {
diff[i] += diff[i - 1];
}
return diff;
給區間 [i, j] 增加 val（可以是負數）：
// 直接操作 diff
diff[i] += val;
if(j + 1 < diff.length) {
diff[j + 1] -= val;
}
例子
lc-1109. 航班預訂統計 * 給你輸⼊⼀個⻓度為 n 的數組 nums，其中所有元素都是 0。再給你輸⼊⼀個 bookings，⾥⾯是若⼲三元組(i,j,k)， * 每個三元組的含義就是要求你給 nums 數組的閉區間 [i-1,j-1] 中所有元素都加上 k。請你返 回最後的 nums 數組是多少？輸入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5 輸出：[10,55,45,25,25]
這個例子初始的原數組全為0，表示 n 個航班初始預定的座位數都為0。對原數組的某些區間有多次加操作，過程如下：
0 0 0 0 0
10 10
20 20
25 25 25 25
--------------------
10 55 45 25 25
-
若採用常規思路，則通過二重循環可以得到結果數組，外循環遍歷每個booking，內循環對每個booking中的區間進行遍歷，區間內的值加上座位數，外循環結束，即可得到結果數組。但該解法最壞情況下時間複雜度為O(m*n)；
public int[] corpFlightBookings(int[][] bookings, int n) { int[] ans = new int[n]; for(int[] nums : bookings) { for(int i = nums[0]; i <= nums[1]; i++) { ans[i - 1] += nums[2]; } } return ans; } 執行用時: 1568 ms 記憶體消耗: 55.3 MB -
採用差分數組，對原數組的某些區間的加操作，全部都注入到差分數組中，最後直接通過差分數組即可得到結果數組。
public int[] corpFlightBookings(int[][] bookings, int n) { // 初始化差分數組（因為原數組初始全為0） int[] diff = new int[n]; // 遍歷二維數組中的每一行 for (int[] b : bookings) { // 把每一行的值賦給i、j、val。數組下標從0開始，而題中是從1開始，為了對應要-1 int i = b[0] - 1, j = b[1] - 1, val = b[2]; // 差分數組左邊界加val（原數組中相當於i後面所有數都加了val） diff[i] += val; // 隔斷右邊界，把j+1後的所有值減去val，上一步加，這一步減，相當於j+1後的值原數組中沒變 if(j + 1 < n) diff[j + 1] -= val; } // 上面循環結束，得到的diff就是差分數組，根據差分數組構造結果數組 int[] res = new int[n]; res[0] = diff[0]; for (int i = 1; i < n; i++) { // 得到結果數組中的每個值 res[i] = res[i - 1] + diff[i]; } return res; } 執行用時: 2 ms 記憶體消耗: 55.7 MB /* 差分數組變化： 0 0 0 0 0 10 0 -10 0 0 // 0 和 1下標加10 10 20 -10 -20 0 // 1 和 2下標加20 10 45 -10 -20 0 // 1 ~ 4下標加25 */時間複雜度：O(m + n)，m 為預定記錄的數量，n 為數組長度；
空間複雜度：O(n)，申請的差分數組diff佔用的空間，其實可以不用申請res，直接把diff當作返回數組，這樣空間可以降到O(1)，因為返回值不計入空間複雜度；
