題目描述:給定整數陣列 arr、整數 k 和整數 threshold,回傳所有長度恰好為 k 且平均值大於等於 threshold 的子陣列數量。
解題思路:使用固定大小的滑動視窗。由於所有子陣列長度固定為 k,可以先計算前 k 個元素的總和作為初始視窗。判斷條件「平均值 >= threshold」等價於「視窗總和 >= k * threshold」,避免浮點數運算。接著每次將視窗向右滑動一格:加入 arr[right],減去 arr[right - k],重新判斷是否滿足條件。這樣每個視窗都只需 O(1) 時間更新,整體線性掃描一遍即可。需注意:初始視窗建立後,從索引 k 開始滑動,共需檢查 n - k + 1 個視窗。
時間複雜度:O(n) — 建立初始視窗 O(k),滑動視窗 O(n - k),合計 O(n)。
空間複雜度:O(1) — 只使用常數個輔助變數,不需要額外陣列。
1. Initialize windowSum = sum of arr[0..k-1], minSum = k * threshold, count = 0. 2. If windowSum >= minSum, increment count. 3. For right from k to n-1: a. Add arr[right] to windowSum. b. Subtract arr[right - k] from windowSum. c. If windowSum >= minSum, increment count. 4. Return count.
方法一:固定大小滑動視窗(最優解) — 如本題解,時間 O(n)、空間 O(1)。利用「平均值 >= threshold 等價於總和 >= k * threshold」避免浮點數,直接整數比較。
方法二:前綴和 — 建立前綴和陣列 prefix,對每個起點 i,計算 prefix[i + k] - prefix[i] 並判斷。時間 O(n)、空間 O(n)。邏輯相同,但需要額外 O(n) 空間存儲前綴和。
方法三:暴力枚舉 — 對每個起點 i,累加 arr[i..i+k-1] 的總和再比較。時間 O(n·k)、空間 O(1)。在 k 很大時效率差,容易超時。
int 儲存視窗總和有什麼風險?如何避免整數溢位?