LeetCode 1652. 拆炸弹
题目链接
1652. 拆炸弹
题目描述
给定一个长度为 n 的循环数组 code 和一个密钥 k，需要替换数组中的每个数字：
- 若
k > 0：第i个数字替换为接下来k个数字的和； - 若
k < 0：第i个数字替换为之前k个数字的和； - 若
k = 0：所有数字替换为0。
数组是循环的，即 code[n-1] 的下一个元素是 code[0]，code[0] 的前一个元素是 code[n-1]。
解法分析：滑动窗口法
核心思路
该解法通过滑动窗口技术高效计算循环数组中连续 k 个元素的和，核心步骤如下：
- 特殊处理
k=0的情况（直接返回全0数组）； - 根据
k的正负确定初始窗口的范围（k>0取后续元素，k<0取前置元素）； - 初始化窗口和，通过滑动窗口动态更新和（减去离开窗口的元素，加上进入窗口的元素）；
- 利用取模操作处理循环数组的边界，确保索引合法。
代码实现
from typing import Listclass Solution:def decrypt(self, code: List[int], k: int) -> List[int]:n = len(code)ans = [0] * n # 结果数组# 若k=0，直接返回全0数组if k == 0:return ans# 确定初始窗口的右边界r# k>0时：窗口为i的后续k个元素，初始右边界r = k + 1# k<0时：窗口为i的前置k个元素，初始右边界r = n（循环数组的特殊处理）r = k + 1 if k > 0 else nk_abs = abs(k) # 统一窗口长度为k的绝对值# 初始化窗口和：窗口为[r - k_abs, r)（左闭右开）s = sum(code[r - k_abs : r])# 滑动窗口计算每个位置的结果for i in range(n):ans[i] = s # 当前窗口和即为ans[i]的值# 更新窗口和：减去离开窗口的元素，加上进入窗口的新元素# 利用取模处理循环数组的边界s += code[r % n] - code[(r - k_abs) % n]r += 1 # 窗口右移return ans
代码解析
-
变量初始化：
n：数组长度；ans：结果数组，初始化为全0；r：窗口的右边界（用于确定窗口范围），根据k的正负动态设置；k_abs：k的绝对值，统一窗口长度（无论k正负，窗口大小都是|k|）。
-
特殊情况处理：
- 若
k = 0，直接返回全0数组（题目要求）。
- 若
-
初始窗口和计算：
- 窗口范围为
[r - k_abs, r)（左闭右开），即包含k_abs个元素； - 当
k > 0时，r = k + 1，窗口初始为code[1...k]（对应第0个元素的后续k个元素）； - 当
k < 0时，r = n，窗口初始为code[n + k ... n - 1]（对应第0个元素的前置|k|个元素，因k为负，n + k = n - |k|）。
- 窗口范围为
-
滑动窗口逻辑：
- 遍历每个索引
i，将当前窗口和s赋值给ans[i]； - 更新窗口和：
- 加上新进入窗口的元素
code[r % n]（r右移后，新元素的索引为r % n，处理循环边界）； - 减去离开窗口的元素
code[(r - k_abs) % n]（窗口左边界的元素，同样用取模处理边界）；
- 加上新进入窗口的元素
r += 1：窗口整体右移，继续计算下一个位置的结果。
- 遍历每个索引
关键逻辑说明
- 窗口范围定义：采用左闭右开区间
[r - k_abs, r)定义窗口，便于滑动时的边界计算（右移时只需更新r即可）。 - 循环数组处理：通过
% n操作确保索引始终在[0, n-1]范围内，完美适配循环数组的首尾相连特性。 - 统一逻辑：无论
k为正或负，均通过调整初始r的值实现窗口的正确定位，后续滑动逻辑完全一致，简化代码。
复杂度分析
- 时间复杂度：
O(n)，其中n是数组长度。初始化窗口和需O(k_abs)时间，滑动窗口遍历n次，每次操作O(1)，总复杂度O(n + k_abs)。由于k_abs ≤ n-1（题目隐含约束），故等价于O(n)。 - 空间复杂度：
O(1)，结果数组ans占用O(n)空间，其他变量为常数级。
示例详解
示例1：code = [5,7,1,4], k = 3（k > 0）
n = 4，k_abs = 3，k > 0故r = 3 + 1 = 4；- 初始窗口为
[4 - 3, 4) = [1, 4)，对应code[1:4] = [7,1,4]，和s = 7 + 1 + 4 = 12；
| 循环i | ans[i] | 窗口更新（s） | r变化 |
|---|---|---|---|
| i=0 | 12 | s += code[4%4=0] - code[(4-3)%4=1] → 12 + 5 - 7 = 10 | r=5 |
| i=1 | 10 | s += code[5%4=1] - code[(5-3)%4=2] → 10 + 7 - 1 = 16 | r=6 |
| i=2 | 16 | s += code[6%4=2] - code[(6-3)%4=3] → 16 + 1 - 4 = 13 | r=7 |
| i=3 | 13 | s += code[7%4=3] - code[(7-3)%4=0] → 13 + 4 - 5 = 12 | r=8 |
最终 ans = [12,10,16,13]，与示例一致。
示例2：code = [1,2,3,4,5,6,7], k = -3（k < 0）
n = 7，k_abs = 3，k < 0故r = 7；- 初始窗口为
[7 - 3, 7) = [4,7)，对应code[4:7] = [5,6,7]（第0个元素的前3个元素），和s = 5 + 6 + 7 = 18；
| 循环i | ans[i] | 窗口更新（s） | r变化 |
|---|---|---|---|
| i=0 | 18 | s += code[7%7=0] - code[(7-3)%7=4] → 18 + 1 - 5 = 14 | r=8 |
| i=1 | 14 | s += code[8%7=1] - code[(8-3)%7=5] → 14 + 2 - 6 = 10 | r=9 |
| i=2 | 10 | s += code[9%7=2] - code[(9-3)%7=6] → 10 + 3 - 7 = 6 | r=10 |
| … | … | … | … |
最终结果符合“每个元素为其前3个元素和”的要求。
总结
该解法通过滑动窗口技术和循环数组的取模处理，高效解决了问题，核心优势在于：
- 逻辑统一：通过调整初始窗口位置，将
k > 0和k < 0的情况合并处理，代码简洁； - 高效滑动：窗口更新仅需
O(1)时间，避免重复计算，总复杂度O(n)； - 边界处理：利用左闭右开区间和取模操作，完美适配循环数组的特性，无边界错误。
该思路是处理“循环数组中连续元素和”问题的经典模板，可推广到类似场景（如循环数组的最大子数组和等）。