当前位置：首页 > article >正文

leetcode 1652. 拆炸弹

article 2025/1/31 2:42:17

题目如下
在这里插入图片描述
数据范围

示例

观察数据范围可知n最多100所以O(n^2)的复杂度也是可以接受的,不过本题更优解还是使用定长滑动窗口。因为每个窗口的和所对应的位置都是对应的，所以我们只需要找到窗口左端点与窗口对应的关系就行。因为本题的k可以小于0所以需要注意左端点与窗口的关系应该分开讨论。

通过代码

class Solution {
public:
    vector<int> decrypt(vector<int>& code, int k) {
        int n = code.size();
        int sum = 0, ak = abs(k);
        vector<int> ans(n, 0);
        if (k == 0)
            return ans;
        for (int i = 0; i < ak; i++) {
            sum += code[i];
        }
        if (k > 0)
            ans[(n - 1) % n] = sum;
        else
            ans[(ak) % n] = sum;
      

        for (int i = 1; i < n; i++) {
            sum += code[(i - 1 + ak) % n];
            sum -= code[i - 1];
            if (k > 0)
                ans[(n + i - 1) % n] = sum;
            else
                ans[(i + ak) % n] = sum;//k小于0时左端点在对应的位置前面(循环数组注意取余)
        }
        return ans;
    }
};