滑动窗口学习

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

题目

问题分析

给定一个数组 nums 和一个整数 k，需要构建一个新的数组 avgs，其中 avgs[i] 表示以 nums[i] 为中心且半径为 k 的子数组的平均值。如果在 i 前或后不足 k 个元素，则 avgs[i] 的值为 -1。

思路

初始化结果数组：创建一个长度与 nums 相同的数组 avgs，初始值全部设为 -1。
滑动窗口计算平均值：
对于每个索引 i，检查其前后是否各有至少 k 个元素。
如果满足条件，计算该窗口内的元素总和并求平均值（使用整数除法）。
将计算得到的平均值存入 avgs[i]。

代码

class Solution:def getAverages(self, nums: List[int], k: int) -> List[int]:n = len(nums)avgs = [-1] * n  # 初始化结果数组if k == 0:return nums  # k 为 0 时，每个元素的平均值就是其本身if 2 * k + 1 > n:return avgs  # 窗口大小大于数组长度，所有位置的平均值为 -1# 计算初始窗口的总和window_sum = sum(nums[:2 * k + 1])for i in range(k, n - k):avgs[i] = window_sum // (2 * k + 1)  # 计算当前窗口的平均值# 更新窗口总和，移除左边元素，加入右边元素if i + k + 1 < n:window_sum += nums[i + k + 1] - nums[i - k]return avgs

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

学习

初始化：avgs = [-1] * n 创建一个全为 -1 的结果数组。
特殊情况处理：
if k == 0: 直接返回 nums，因为每个元素的平均值就是其本身。
if 2 * k + 1 > n: 返回全为 -1 的数组，因为窗口大小超过了数组长度。
滑动窗口：
window_sum = sum(nums[:2k+1]) 计算初始窗口（从 0 到 2k）的总和。
for i in range(k, n - k): 遍历每个有效中心位置 i。
avgs[i] = window_sum // (2 * k + 1) 计算当前窗口的平均值。
window_sum += nums[i + k + 1] - nums[i - k] 更新窗口总和，移除左边元素，加入右边元素。