題目鏈接

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 的子數組的和；
• 求滑動窗口內元素的平均值或其他統計量（需調整窗口大小和計算邏輯）。

通過滑動窗口技術，可高效解決此類問題，是處理定長子數組問題的經典模板之一。