題目描述:給定整數陣列 nums 和整數 k,回傳陣列 averages,其中 averages[i] 為以索引 i 為中心、半徑 k 的子陣列(即 nums[i-k..i+k],共 2k+1 個元素)的平均值(向下取整)。若索引 i 距離陣列邊界不足 k(即 i < k 或 i + k >= n),則 averages[i] = -1。
解題思路:使用固定大小為 2k+1 的滑動視窗。首先將 averages 初始化為全 -1。若 n < 2k+1,則所有位置都無法滿足條件,直接回傳。否則,先計算初始視窗(索引 0 到 2k)的總和。初始視窗的中心索引為 k,設定 averages[k] = windowSum / (2k+1)。接著從中心索引 k+1 開始向右滑動:每次加入 nums[center + k]、移除 nums[center - k - 1],更新 windowSum 後,設定 averages[center] = windowSum / (2k+1)。需注意使用 long long 避免 2k+1 個元素(最多 10⁵ 個,每個最大 10⁵)相加溢位整數範圍(最大可達 10¹⁰)。
時間複雜度:O(n) — 建立初始視窗 O(2k+1) = O(k),滑動視窗掃描 O(n - 2k) = O(n),合計 O(n)。
空間複雜度:O(1) — 不計回傳陣列 averages(題目要求輸出),額外只用常數個輔助變數。若計入輸出,則為 O(n)。
1. Initialize averages = array of n elements, all -1. 2. Set windowSize = 2 * k + 1. 3. If n < windowSize, return averages immediately. 4. Compute windowSum = sum of nums[0..2k]. 5. Set averages[k] = windowSum / windowSize. 6. For center from k+1 to n-1-k: a. Add nums[center + k] to windowSum. b. Subtract nums[center - k - 1] from windowSum. c. Set averages[center] = windowSum / windowSize. 7. Return averages.
方法一:固定大小滑動視窗(最優解) — 如本題解,時間 O(n)、空間 O(1)(不計輸出)。使用 long long 防止溢位是關鍵細節。
方法二:前綴和 — 建立前綴和陣列 prefix(需用 long long),對每個合法中心 i,計算 (prefix[i + k + 1] - prefix[i - k]) / windowSize。時間 O(n)、空間 O(n)。邏輯相同但需額外 O(n) 空間,且建立前綴和時需小心索引偏移。
方法三:暴力枚舉 — 對每個合法中心 i,逐一加總 nums[i-k..i+k]。時間 O(n·k)、空間 O(1)。在 k 接近 n/2 時效率降為 O(n²),無法通過大測資。
long long 避免溢位,如果只用 int,最大輸入下溢位會在什麼情況下發生?能舉出一個具體的反例嗎?