题目链接

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

题目描述

给定一个下标从 0 开始的整数数组 nums 和整数 k，构建并返回一个长度为 n 的数组 avgs，其中 avgs[i] 表示以下标 i 为中心、半径为 k 的子数组的平均值。具体规则如下：

• 无效位置：若 i 左侧不足 k 个元素（i - k < 0）或右侧不足 k 个元素（i + k >= n），则 avgs[i] = -1；
• 有效位置：若 i 前后均有至少 k 个元素（即子数组下标范围为 [i-k, i+k]，共 2k+1 个元素），则 avgs[i] 为该子数组元素的平均值（使用截断式整数除法，直接舍去小数部分）。

解法分析

代码实现

from typing import List  class Solution:  def getAverages(self, nums: List[int], k: int) -> List[int]:  s = 0  # 滑动窗口内元素的和  ans = [-1] * len(nums)  # 初始化结果数组，默认所有位置无效  for i in range(len(nums)):  s += nums[i]  # 将当前元素加入窗口和  if i < k * 2:  continue  # 窗口未形成完整长度时跳过计算  ans[i - k] = s // (2 * k + 1)  # 计算中心位置的平均值  s -= nums[i - 2 * k]  # 滑动窗口，移除左边界元素  return ans  

代码详细分析

1. 初始化操作

• s（窗口和）：用于存储当前滑动窗口内所有元素的和，初始化为 0。随着遍历进行，逐个累加数组元素，并在窗口滑动时减去离开窗口的元素，保持动态更新。
• ans（结果数组）：初始化为全 -1，表示所有位置默认无效。后续有效位置会被覆盖为对应的平均值，无需额外处理无效位置的边界条件。

2. 遍历数组与窗口扩展

• 右指针 i：从 0 开始遍历数组的每个元素，每次将 nums[i] 加入窗口和 s，相当于将窗口的右边界扩展到当前元素 i。
• 窗口形成条件：当 i < 2k 时，窗口内元素个数为 i+1，而有效窗口需要 2k+1 个元素（例如 k=1 时需要3个元素，i=1 时只有2个），此时跳过计算，继续扩展窗口。

3. 有效窗口处理

• 窗口完整时：当 i >= 2k 时，窗口包含从 i-2k 到 i 的 2k+1 个元素（例如 k=3，i=6 时，窗口范围是 [0,6]，共7个元素），此时窗口以 i-k 为中心（左边界 i-2k 右移 k 步到达中心）。
• 平均值计算：使用截断式整数除法 s // (2k+1)，直接舍去小数部分，符合题目要求。

4. 窗口滑动更新

• 移除左边界元素：在计算完当前中心位置的平均值后，下一个窗口的左边界需要右移一位，即移除 nums[i-2k]（当前窗口的最左元素），确保下一次遍历的窗口大小仍为 2k+1。例如，当 i=6 处理完后，下一个窗口左边界从 0 变为 1，窗口范围变为 [1,7]。

案例分析

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

分步计算过程

1. 窗口大小：2k+1 = 7，有效中心位置需满足 i-3 >= 0 且 i+3 < 9，即 i ∈ [3, 5]（对应结果数组下标3、4、5）。

2. 遍历过程：

   • 当 i=6（下标6，元素5）：
     • 窗口和 s = 7+4+3+9+1+8+5 = 37；
     • i >= 2k=6，中心位置为 6-3=3，ans[3] = 37 // 7 = 5；
     • 移除左边界元素 nums[0]=7，s = 37-7=30。
   • 当 i=7（下标7，元素2）：
     • 加入当前元素2，s = 30+2=32；
     • 中心位置为 7-3=4，ans[4] = 32 // 7 = 4；
     • 移除左边界元素 nums[1]=4，s = 32-4=28。
   • 当 i=8（下标8，元素6）：
     • 加入当前元素6，s = 28+6=34；
     • 中心位置为 8-3=5，ans[5] = 34 // 7 = 4；
     • 移除左边界元素 nums[2]=3，但遍历结束，无需继续处理。

3. 结果数组：

   • 无效位置（如 i=0,1,2,6,7,8 因边界不足）保持初始值 -1，有效位置 3、4、5 分别赋值为 5、4、4，最终结果与示例一致。

总结

方法优势

• 线性时间复杂度：O(n)，每个元素仅被访问一次，窗口滑动和计算平均值均为常数时间操作，避免了暴力解法中每次计算子数组和的 O(k) 复杂度。
• 简洁的边界处理：通过初始化结果数组为 -1，自动处理所有无效位置，无需额外判断 i-k < 0 或 i+k >= n，代码逻辑清晰。
• 空间高效：除结果数组外，仅使用常数级额外空间（s 和循环变量），适用于处理大规模数据（如 n=10^5）。

关键细节

• 窗口长度：固定为 2k+1，确保覆盖中心 i 左右各 k 个元素。
• 整数除法：使用 // 运算符实现截断式除法，直接舍去小数部分，符合题目要求（例如 37//7=5，而非四舍五入）。
• 滑动窗口逻辑：每次右边界扩展后，仅当窗口完整时（i >= 2k）才计算中心位置，避免无效计算。

适用场景

该解法适用于所有「固定长度子数组求均值/和」的问题，例如：

• 求每个长度为 m 的子数组的和；
• 求滑动窗口内元素的平均值或其他统计量（需调整窗口大小和计算逻辑）。

通过滑动窗口技术，可高效解决此类问题，是处理定长子数组问题的经典模板之一。