LeetCode 1652. 拆炸彈（環形陣列＋定長滑動視窗圖解）

1652. 拆炸彈

題目描述

你有一個炸彈需要拆除，時間緊迫！你的情報員會給你一個長度為 n 的循環陣列 code 以及一個密鑰 k。

為了獲得正確的密碼，你需要替換掉每一個數字。所有數字會同時被替換。

• 如果 k > 0，將第 i 個數字用接下來 k 個數字之和替換。
• 如果 k < 0，將第 i 個數字用之前 k 個數字之和替換。
• 如果 k == 0，將第 i 個數字用 0 替換。

由於 code 是循環的，code[n-1] 下一個元素是 code[0]，且 code[0] 前一個元素是 code[n-1]。

給你循環陣列 code 和整數密鑰 k，請你回傳解密後的結果來拆除炸彈！

範例 1

輸入：code = [5,7,1,4], k = 3
輸出：[12,10,16,13]
解釋：每個數字都被接下來 3 個數字之和替換。
解密後的密碼為 [7+1+4, 1+4+5, 4+5+7, 5+7+1]。注意到陣列是循環連接的。

範例 2

輸入：code = [1,2,3,4], k = 0
輸出：[0,0,0,0]
解釋：當 k 為 0 時，所有數字都被 0 替換。

範例 3

輸入：code = [2,4,9,3], k = -2
輸出：[12,5,6,13]
解釋：解密後的密碼為 [3+9, 2+3, 4+2, 9+4]。
注意到陣列是循環連接的。如果 k 是負數，那麼和為之前的數字。

限制

• n == code.length
• 1 <= n <= 100
• 1 <= code[i] <= 100
• -(n - 1) <= k <= n - 1

本文題解思路與程式碼整理自 LeetCode 題解作者「灵茶山艾府」，題解連結。圖解與步驟說明為自行補充。

前置知識：定長滑動視窗

定長視窗每次右移一格，少一個最左邊的元素、多一個新元素，視窗內的和可以用「加新的、減舊的」在 O(1) 內更新。前面幾篇已經用過，例如 2841。上一篇 2134 也處理過環形陣列，下標超過 n − 1 就取模 n。

思路

這題的條件看起來有三種（k > 0、k < 0、k == 0），其實可以統一成「一個長度為 |k| 的視窗往右滑」。

第一步：每個位置要加總的是哪一段

• k > 0：ans[i] 是 i 後面緊接著的 k 個數字之和，也就是下標 i + 1 ~ i + k。
• k < 0：ans[i] 是 i 前面的 |k| 個數字之和，也就是下標 i − |k| ~ i − 1。
• k == 0：什麼都不加，結果是 0。

因為陣列是循環的，下標超出範圍時取模 n 繞回來。

按「下一格」逐格看每個 ans[i] 用的是哪一段，也可以切換範例：

選一個範例：範例 1：k = 3範例 3：k = −2範例 2：k = 0

上一格 下一格 重置

解密結果 ans

這一格要加總的窗口（長度 |k|） 目前要被替換的位置 i

先看範例 1（k = 3）：ans[0] = 後面 3 個 = 7 + 1 + 4；ans[1] = 1 + 4 + 5（窗口開始繞回開頭）。

再看範例 3（k = −2）：ans[0] = 前面 2 個。0 的前面要繞回尾巴，所以是 code[3] + code[2] = 3 + 9 = 12，和題目寫的 [3+9, …] 一致。

第二步：不管 k 的正負，窗口都是向右移動

這題最關鍵的觀察：

無論 k > 0 還是 k < 0，算完 ans[i] 再算 ans[i + 1] 時，窗口都是向右移動一格，只有「第一個窗口」的位置不同，窗口大小都是 |k|。

所以只要找到第一個窗口的下標範圍，就可以直接開始滑：

• k > 0：ans[0] 用的是下標 1 ~ k，用左閉右開寫成 [1, k + 1)。
• k < 0：ans[0] 用的是下標 n − |k| ~ n − 1（0 的前面繞回尾巴），寫成 [n − |k|, n)。
• 窗口大小都是 |k|。

例如 code = [3,1,4,1,5,9]，k = 3：

要算的	窗口	怎麼算
ans[0]	[1,4,1]	1 + 4 + 1 = 6
ans[1]	[4,1,5]	在上一個基礎上加 code[4] = 5、減 code[1] = 1：6 + 5 − 1 = 10
ans[2]	[1,5,9]	加 code[5] = 9、減 code[2] = 4：10 + 9 − 4 = 15
ans[3]	[5,9,3]	加 code[6 mod 6] = code[0] = 3、減 code[3] = 1：15 + 3 − 1 = 17
ans[4]	[9,3,1]	加 code[7 mod 6] = code[1] = 1、減 code[4] = 5：17 + 1 − 5 = 13
ans[5]	[3,1,4]	加 code[8 mod 6] = code[2] = 4、減 code[5] = 9：13 + 4 − 9 = 8

第三步：用右開端點 r 管理窗口

用 r 表示窗口的右開端點（窗口是 [r − |k|, r)）：

• 第一個窗口：k > 0 時 r = k + 1；k < 0 時 r = n。
• 窗口向右滑動：移入的元素下標是 r mod n，移出的元素下標是 (r − |k|) mod n，然後 r++。
• 每一輪先把目前的窗口和 s 寫進 ans[i]，再更新窗口，為下一輪準備。

k == 0 時窗口大小是 0，第一個窗口和是 0，每次移入、移出的是同一個元素（code[r % n] − code[(r − 0) % n] = 0），s 一直是 0，所以不需要特判。

圖解（可互動）

下面逐步看 r、窗口和 s 怎麼變化，上方是 code，下方是逐格填入的 ans。可以切換 k = 3（題解範例）和 k = −2（範例 3）。注意：

• 先算第一個窗口，k > 0 時是 [1, k + 1)，k < 0 時是 [n − |k|, n)。
• 每一步先把目前的窗口和寫進 ans[i]，再移入、移出元素。
• r 超過 n 之後，用 r % n 繞回去。

選一個範例：k = 3（題解範例）k = −2（範例 3）

上一步 下一步 重置

解密結果 ans

目前窗口 入 = 下一步移入 出 = 下一步移出

窗口和 s0

右開端點 r0

解法（灵茶山艾府）

class Solution {
    public int[] decrypt(int[] code, int k) {
        int n = code.length;
        // 計算第一個視窗的右開端點
        int r = k > 0 ? k + 1 : n;
        k = Math.abs(k);

        // 計算第一個視窗的元素和
        int s = 0;
        for (int i = r - k; i < r; i++) {
            s += code[i];
        }

        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = s;
            s += code[r % n] - code[(r - k) % n];
            r++;
        }
        return ans;
    }
}

幾個細節：

• r 要在 k = Math.abs(k) 之前算：r 需要 k 原本的正負，順序反了就錯。
• 計算第一個窗口時，下標 r − k ~ r − 1 不用取模：k > 0 時範圍是 1 ~ k，k < 0 時是 n − |k| ~ n − 1，都在 [0, n − 1] 內。
• 滑動時移入的 code[r % n] 要取模；移出的 code[(r − k) % n] 也取模，因為這裡 k 已經是絕對值，r − k 在後面幾輪可能超過 n。
• k == 0 不用特判，s 一直是 0。

複雜度分析

• 時間複雜度：O(n)，其中 n 是 code 的長度。算第一個窗口最多 O(n)，之後迴圈 n 次，每次 O(1)。
• 空間複雜度：O(1)。回傳值不計入。