陈东宇的博客

    2090. 半径为 k 的子数组平均值

    力扣原题（完整题面）

    题意

    对数组中的每个位置 i，取以它为中心、向左右各延伸 k 个元素的连续子数组，计算这 2k + 1 个数的整数平均值。如果某一侧没有足够的元素，该位置的答案就是 -1。

    样例 1

    输入：nums = [7,4,3,9,1,8,5,2,6], k = 3
输出：[-1,-1,-1,5,4,4,-1,-1,-1]

    解释：下标 0、1、2 的前面不足 3 个元素，下标 6、7、8 的后面不足 3 个元素，所以这些位置都是 -1。其余三个位置的平均值分别为：

    • avg[3] = (7+4+3+9+1+8+5) / 7 = 37 / 7 = 5；
    • avg[4] = (4+3+9+1+8+5+2) / 7 = 4；
    • avg[5] = (3+9+1+8+5+2+6) / 7 = 4。

    样例 2

    输入：nums = [100000], k = 0
输出：[100000]

    解释：下标 0 的半径为 0 的子数组只包含 100000，因此 avg[0] = 100000 / 1 = 100000。

    样例 3

    输入：nums = [8], k = 100000
输出：[-1]

    解释：下标 0 的前后都不足 100000 个元素，因此 avg[0] = -1。

    解题思路（前缀和）

    先计算前缀和，令 preSum[i] 表示从 nums[0] 到 nums[i] 的总和。以 i 为中心的窗口范围是 [i-k, i+k]：

    • 当 i-k > 0，窗口和为 preSum[i+k] - preSum[i-k-1]。
    • 当 i-k == 0，窗口从数组开头算起，窗口和就是 preSum[i+k]。

    只有 k <= i < n-k 的位置能形成完整窗口。前缀和使用 long long，因为数组元素的总和可能超过 int 的范围。

    我的代码

    class Solution {
public:
    vector<int> getAverages(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long> preSum(n, 0);
        preSum[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            preSum[i] = preSum[i - 1] + nums[i];
        }

        int start = k;
        int end = n - k;
        vector<int> ans(n, 0);
        for (int i = 0; i < n; ++i) {
            if (i < start || i >= end) {
                ans[i] = -1;
            } else {
                if (i - k - 1 < 0) {
                    ans[i] = preSum[i + k] / (k * 2 + 1);
                } else {
                    ans[i] = (preSum[i + k] - preSum[i - k - 1]) / (k * 2 + 1);
                }
            }
        }
        return ans;
    }
};

    时间复杂度 O(n)，空间复杂度 O(n)，主要空间用在前缀和与返回数组上。

    滑动窗口解法

    窗口长度固定为 2k + 1，中心每次右移一格，窗口也只是右移一格——出窗口、进窗口的各只有一个元素，边走边维护窗口和即可，不需要前缀和数组：

    • 先累加出第一个窗口 [0, 2k] 的和，答案从中心 i = k 开始有效；
    • 每轮记录 ans[i] = sum / len 后，窗口右移：加上右端新进来的 nums[i+k+1]，减去左端出去的 nums[i-k]；
    • 两侧凑不满 2k + 1 个元素的位置保持 -1（ans 初始化为 -1）；
    • 窗口和用 long long，防止元素总和超过 int 范围。
    class Solution {
public:
    vector<int> getAverages(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> ans(n, -1);
        int len = 2 * k + 1;
        if (n < len) return ans;   // 连第一个窗口都凑不出来

        long long sum = 0;
        for (int i = 0; i < len; ++i) {    // 第一个窗口 [0, 2k]
            sum += nums[i];
        }
        for (int i = k; i + k < n; ++i) {
            ans[i] = sum / len;
            if (i + k + 1 < n) {           // 窗口右移一格
                sum += nums[i + k + 1] - nums[i - k];
            }
        }
        return ans;
    }
};

    时间复杂度 O(n)，空间复杂度 O(1)（不算返回数组）。相比前缀和解法省掉了 O(n) 的前缀和数组，这也是定长窗口最典型的"进一个、出一个"套路。