1 題目描述

找到一個subarray的和大於等於target，並且這個subarray的長度是最小的。

2 解法

因為要找出最小長度，基本上就是找到一組window大小為最小，但是同時滿足>=target的條件。因為nums是無序的，所以一定是要遍歷一次，因此時間複雜度是O(N)。
老樣子，Sliding Window 就是需要定義出以下狀況：

1. 何時停止擴展？
   • 我們希望當前的window >= target時，停止擴展
   • 在還沒超過target之前，我們會一直擴展window
   • right 指針會一直往右移動
2. 處理當前window的時機？
   • 因為接下來我們要開始收縮window找找看有沒有更小的window
   • 計算當前window的總和數，以及當前window的長度是否有小於最小長度
3. 何時收縮window？
   • 如果發現當前window的總和數 >= target，就開始收縮window
   • 移動left指針，並且更新當前window的總和數
   • 當當前window的總和數 < target，就停止收縮window

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    """
    time: O(N)
    space: O(1)
    """
    def minSubArrayLen2(self, target: int, nums: List[int]) -> int:
        l, min_len = 0, float('inf')
        tot = 0
        # right 指針會一直往右移動 擴展window
        for r in range(len(nums)):
            tot += nums[r]
            # 一但發現>=target，就開始收縮window尋找最佳解
            while tot >= target:
                # 更新最小長度
                min_len = min(min_len, r - l + 1)
                # 縮小長度，扣掉不在windows內的數字
                tot -= nums[l]
                # 移動左指針
                l += 1
        return min_len if min_len != float('inf') else 0        

3 總結

這題不難，但是我卡在如何要擴展window的時機，因為當初使用while來寫，但是這題不應該使用while，因為他不是two pointer從頭跟尾來縮window，他是two pointer從左到右來擴展跟收縮window。要檢查到right pointer觸底為止，所以不需要while。你也不用思考何時要right+1，因為for會處理掉這件事情。