題目描述:給定正整數陣列 nums 和正整數 target,找出元素和大於等於 target 的最短連續子陣列,回傳其長度。若不存在,回傳 0。
解題思路:使用滑動視窗(Sliding Window)。維護左指針 left 和右指針 right,以及視窗內的當前總和 windowSum。右指針不斷向右擴展並累加 nums[right]。每當 windowSum >= target 時,記錄當前視窗長度並嘗試縮短視窗——將 nums[left] 從總和中減去,左指針右移,反覆直到 windowSum < target。由於陣列元素均為正數,縮小視窗必定使總和減少,這保證了滑動視窗的正確性。整個過程 left 和 right 各只走一遍陣列,線性時間完成。
時間複雜度:O(n) — right 和 left 各最多移動 n 次,總操作次數為 O(2n) = O(n)。
空間複雜度:O(1) — 只使用常數個輔助變數,不需要額外陣列。
1. Initialize left = 0, windowSum = 0, minLen = infinity.
2. For right from 0 to n-1:
a. Add nums[right] to windowSum.
b. While windowSum >= target:
- Update minLen = min(minLen, right - left + 1).
- Subtract nums[left] from windowSum.
- Increment left.
3. If minLen is still infinity, return 0; otherwise return minLen.方法一:滑動視窗(最優解) — 如本題解,時間 O(n)、空間 O(1)。只適用於所有元素為正數的情況(保證縮視窗時總和單調遞減)。
方法二:前綴和 + 二分搜尋 — 預先建立前綴和陣列 prefix,對每個右端點 r,二分搜尋找最小的左端點 l 使得 prefix[r] - prefix[l] >= target。時間 O(n log n)、空間 O(n)。可處理不含負數的一般情況。
方法三:暴力枚舉(Brute Force) — 枚舉所有子陣列,時間 O(n²)、空間 O(1)。簡單但效率差,大輸入會超時。