[每日一题] 1652.拆炸弹

博主： Richard
发布时间：2024 年 05 月 06 日
118 次浏览
暂无评论
537字数
分类： LeetCode

> https://leetcode.cn/problems/defuse-the-bomb/description/?envType=daily-question&envId=2024-05-02

简单题，滑动窗口维护一个 `sum` 变量用来记录区间内数组的和即可。循环数组可以通过取模来实现，或者将原数组大小翻倍。

这里通过取模来实现循环数组。

```c++
class Solution {
public:
    std::vector<int> decrypt(std::vector<int>& code, int k) {
        const int n = code.size();
        
        if (k == 0)
            return std::vector<int>(n);
        
        int sum = 0, left, right;
        std::vector<int> res(n);

if (k > 0) {
            left = 1, right = k;
            for (int i = 1; i <= k; ++i)
                sum += code[i];
        } else {
            left = n + k, right = n - 1;
            for (int i = left; i < n; ++i)
                sum += code[i];
        }
            
        res[0] = sum;
        for (int i = 1; i < n; ++i) {
            sum -= code[left];
            left = (left + 1) % n;
            right = (right + 1) % n;
            sum += code[right];
            res[i] = sum;
        }
        
        return res;
    }
};
```

- 时间复杂度：$O(n)$ ，其中 $n$ 为数组 `code` 的长度。
- 空间复杂度：$O(1)$ 。

最后修改：2024 年 05 月 06 日