【Leetcode Daily】1652拆炸弹

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个整型数组加一个数字 k，按照 k 的值重新生成一个数组，比如 k 为正数，那么数组的每个下标要同时替换为其后面 k 个数之和；k 为附属，则换为其前面 k 个数之和。

思路分享

• 同时这个关键词说明，各个替换互不影响，正是因此，可以用定长滑动窗口来解决。

• 嘛，还是简单提一下暴力解法，就是先遍历每一位，按照 k 的情况，对每一位设立循环找前或后的数字之和。由于二重循环，时间复杂度就达到了 O(n^2)

• 那么滑动窗口解法首先要找到 k 不同情况下，首个窗口的范围。经测试，第一个窗口右侧的坐标在 k 正数时，会设置为 k+1，而 k 为负数时设为 n。而左侧坐标一直是右侧坐标减去 k 即可。（这里的窗口都是左闭右开的）后续窗口都是右移，参照模板即可（【Leetcode Daily】1456定长子串中元音的最大数目

  https://leetcode.cn/problems/defuse-the-bomb/solutions/2765762/on-ding-chang-hua-dong-chuang-kou-python-y2py/

代码解答（强烈建议自行解答后再看）

• 参照的解法

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

        vector<int> ans(n);

        int right = k > 0 ? k+1 : n; // 第一个窗口右边的下标

        k = abs(k);

        int s = reduce(code.begin() + right - k, code.begin() + right);
        
        for (int i = 0; i < n; i++) {
            ans[i] = s;
            s += code[right % n] - code[(right - k) % n]; 
            right++;
        } 

        return ans;
    }
};