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

题目描述#

给你一个下标从 0 开始的数组 nums 和一个整数 k。

半径为 k 的子数组平均值是指：对每个下标 i，以下标 i 为中心，半径为 k 的子数组（共 2k+1 个元素）的平均值向下取整。

返回数组 avgs，其中 avgs[i] 是对应下标的平均值，如果无法找到半径为 k 的子数组则返回 -1。

示例 1：

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

示例 2：

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

提示：

n == nums.length
1 <= n <= 10^5
0 <= k <= n
0 <= nums[i] <= 10^5

解法思路#

定长滑动窗口——本题的窗口不是长度 k，而是一个长度为 2k+1 的窗口（以下标 i 为中心，左界 i-k，右界 i+k）。关键在「把新题往模板上靠」：把窗口长度识别成 2k+1，就回归到熟悉的定长滑窗套路。

边界处理：只有当 k <= i <= n-k-1 时，长度为 2k+1 的子数组才能完整地落在数组中。因此：

初始化答案数组全为 -1，只有能形成完整窗口的位置才需要计算；
若 2k+1 > n，任意下标都无法形成完整窗口，直接返回全 -1；
若 k == 0，窗口就是元素本身，直接返回原数组。

掩盖「窗口右移对应中心回填」这一细节：落在完整窗口内的下标与窗口右端点不同——右端点进一位，窗口中心才前进一位。所以用右端点指针遍历时，当前窗口 [i-2k, i] 的中心是 i-k，平均值要回填到 avgs[i-k]。

沿用 入-更新-出 三步（同时维护窗口和，避免重复求和）：

入：右端点 nums[i] 进入窗口，s += nums[i]；窗口不足 2k+1 时继续。
更新：窗口长度为 2k+1，记录 avgs[i-k] = s // (2k+1)。
出：左端点 nums[i-2k] 离开窗口，s -= nums[i-2k]。

逐步举例（nums = [7,4,3,9,1,8,5,2,6], k = 3，窗口长 2k+1=7）。中心 i 只能在 [3, 5] 形成完整窗口，故首尾 3 个下标返回 -1：

先统计前 7 个元素 [7,4,3,9,1,8,5] 之和 s = 37，其中心是 9(下标3)，回填 avgs[3] = 37//7 = 5。
右移一步：出 7、入 2 → [4,3,9,1,8,5,2]，s = 32，中心 1(下标4)，avgs[4] = 32//7 = 4。
再右移：出 4、入 6 → [3,9,1,8,5,2,6]，s = 34，中心 8(下标5)，avgs[5] = 34//7 = 4。

最终 avgs = [-1,-1,-1,5,4,4,-1,-1,-1]，与预期一致。注意窗口每右移一位，中心只前进一位，故回填位置是 i-k。

思路与写法参考灵茶山艾府《【模板】定长滑动窗口》（入-更新-出套路）及 2090 对应题解。

复杂度分析#

时间复杂度：O(n)，每个元素进/出窗口各一次。
空间复杂度：O(n)，用于返回答案数组。

代码实现#

1
class Solution:
2
    def getAverages(self, nums: list[int], k: int) -> list[int]:
3
        n = len(nums)
4
        ans = [-1] * n
5
        if k == 0:
6
            return nums
7
        if n < 2 * k + 1:
8
            return ans
9
        window = 2 * k + 1
10
        cur = sum(nums[:window])
11
        ans[k] = cur // window
12
        for i in range(k + 1, n - k):
13
            cur += nums[i + k] - nums[i - k - 1]
14
            ans[i] = cur // window
15
        return ans

1
import unittest
2

3

4
class TestGetAverages(unittest.TestCase):
5
    def setUp(self):
6
        self.solution = Solution()
7

8
    def test_example1(self):
9
        self.assertEqual(
10
            self.solution.getAverages([7, 4, 3, 9, 1, 8, 5, 2, 6], 3),
11
            [-1, -1, -1, 5, 4, 4, -1, -1, -1],
12
        )
13

14
    def test_example2(self):
15
        self.assertEqual(self.solution.getAverages([100000], 0), [100000])
16

17
    def test_small_array(self):
18
        self.assertEqual(self.solution.getAverages([1, 2], 1), [-1, -1])
19

20

21
if __name__ == "__main__":
22
    unittest.main()