基本資料#
難易度：中等 第一次嘗試：2025-08-09
- 總花費時間：00:00.00
解題思路#
這題屬於滑動視窗。用右指針累加視窗總和，當總和大於等於 target 時，開始從左邊縮小視窗，試著在仍符合條件的前提下把長度壓到最短。
解法#
- 維護區間
[left, right]與window_sum。 - 每次右移
right就把nums[right]加進window_sum。 - 只要
window_sum ≥ target，就更新答案，並持續右移left同時扣除nums[left]，以取得更短的合法視窗。
from typing import List
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
left = 0
window_sum = 0
min_length = float("inf")
for right, value in enumerate(nums):
window_sum += value
while window_sum >= target:
min_length = min(min_length, right - left + 1)
window_sum -= nums[left]
left += 1
return 0 if min_length == float("inf") else min_length
複雜度#
- 時間：O(n)
- 空間：O(1)
收穫#
- 所有數字為正時，滑動視窗才能單調縮小並保證不會漏解。
- 不變量：一旦
window_sum ≥ target，就嘗試移動left以縮短視窗。 - 另一種作法是前綴和 + 二分搜尋，時間 O(n log n)，但本題滑動視窗已是最佳。