1652. 拆炸弹

题意

有一个循环数组 code 和密钥 k，按规则解密得到新数组 ans：

k > 0：ans[i] 是 code 中第 i 个位置后面 k 个数字的和；
k < 0：ans[i] 是 code 中第 i 个位置前面 |k| 个数字的和；
k == 0：ans[i] = 0。

因为是循环数组，越界后要绕回头尾继续数。

样例 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]

解释：每个数字都由之前 2 个数字之和替换，结果为 [3+9, 2+3, 4+2, 9+4]。数组首尾循环相连。

解题思路（前缀和）

循环数组的麻烦在于下标会绕圈，直接取模容易在边界出错。这里把数组首尾相连复制三份，问题就变成了普通数组上的区间和：

用长度为 3n 的数组算前缀和，其中 code[i % n] 让复制部分自动取到原数组；
真正的答案只从中间那份（下标 n ~ 2n-1）取。对中间的某个位置 i，它无论往左还是往右延伸 k 个，需要的下标都不会越过 [0, 3n) 的范围，不用做任何取模修正；
k > 0 时窗口是 [i, i+k]（不含自己，含右端），和为 preSum[i+k] - preSum[i]；
k < 0 时窗口是 [i+k, i-1]，和为 preSum[i-1] - preSum[i+k-1]；
k == 0 时不需要额外处理，ans 初始就是 0。

我的代码

class Solution {
public:
    vector<int> decrypt(vector<int>& code, int k) {
        int n = code.size();
        vector<int> preSum(3 * n, 0);  // 复制两个数组首尾相连，整个数组长度变为3n，记录前缀和
        preSum[0] = code[0];
        for (int i = 1; i < 3 * n; ++i) {
            preSum[i] = preSum[i - 1] + code[i % n];  // 前缀和，因为首尾相连，所以取模后code[n]=code[0]
        }
        vector<int> ans(n, 0);
        for (int i = n; i < 2 * n; ++i) {
            if (k < 0) {
                ans[i - n] = preSum[i - 1] - preSum[i + k - 1];
            } else if (k >= 0) {
                ans[i - n] = preSum[i + k] - preSum[i];
            }
        }
        return ans;
    }
};

时间复杂度 O(n)（准确说是 O(3n)），空间复杂度 O(n)，主要开销在 3n 的前缀和数组上。

滑动窗口解法

其实每个位置要的就是一段定长为 |k| 的区间和，相邻两个位置的窗口只差"出去一个、进来一个"，完全可以用滑动窗口维护，不需要 3n 的前缀和数组：

设 m = |k|。k > 0 时位置 i 的窗口是 (i, i+m]，起点从 1 开始；k < 0 时窗口是 [i-m, i)，起点从 n+k 开始（保证落在 [0, n) 内）；
先累加出 i = 0 的第一个窗口和；
之后每轮先记录答案，再把窗口整体向后挪一格：减去离开的 code[begin+i]，加上进入的 code[begin+i+m]，下标对 n 取模即可；
k == 0 直接返回全 0。

class Solution {
public:
    vector<int> decrypt(vector<int>& code, int k) {
        int n = code.size();
        vector<int> ans(n, 0);
        if (k == 0) return ans;

        int m = abs(k);                    // 窗口长度
        int begin = k > 0 ? 1 : n + k;     // 第一个窗口的起点
        int sum = 0;
        for (int j = 0; j < m; ++j) {      // 先凑出 i = 0 的窗口
            sum += code[(begin + j) % n];
        }
        for (int i = 0; i < n; ++i) {
            ans[i] = sum;
            sum = sum - code[(begin + i) % n] + code[(begin + i + m) % n];
        }
        return ans;
    }
};

时间复杂度 O(n)，空间复杂度 O(1)（不算返回数组）。对比前缀和解法省掉了 3n 的辅助数组，是这道题作为定长窗口练习的"标准姿势"。

#1652. 拆炸弹

#题意

#样例 1

#样例 2

#样例 3

#解题思路（前缀和）

#我的代码

#滑动窗口解法