209. Minimum Size Subarray Sum

題目連結

思路

本題的題目要在一個陣列裡面尋找滿足條件的最小子陣列。延續雙指標的運用，此題想要帶出另一個常見的滑動視窗的概念，也就是透過快慢指針的移動，降低運算的時間複雜度。像是本題用暴力硬解的話 (兩個 for 迴圈檢查所有子陣列) 大約會是 $O(n^2)$ 的複雜度，但若是加入滑動視窗的方法的話可以將複雜度降到 $O(n)$。

對於滑動視窗來說，處理起始和結尾指標的移動是至關重要的部分。在本題的情境裡，結尾指標會是從陣列一開始慢慢往後移動，而起始的指標要如何處理呢？這就和題目所求的條件有所關聯了，當結尾指標往前走直到當視窗內的數值總和大於等於 target 的時候，就需要去檢查當下的子陣列長度是否小於目前的最小長度，如果是的話就將其更新到最小長度上面，並且在此時將起始指標向後移動，扣掉對應的值，可以參考下面這個簡易的小動圖呈現出來的樣子~

可以觀察到 end 會一直持續的往後走，而 start 則是當 sum 滿足 target 的要求時才會開始前進，等到 sum 被扣到小於 target 的時候才會停止，讓 end 繼續往前走。因此實作上就是以這樣的概念來進行，而最小長度的初始值只要設定成比原始陣列的長度還要大基本上就沒有問題。

Full Code

Golang

func minSubArrayLen(target int, nums []int) int {
    sum := 0
    minLen := len(nums) + 1

    for start, end := 0, 0; end < len(nums); end++ {
        sum += nums[end]
        for sum >= target {
            currentLen := end - start + 1
            if currentLen <= minLen {
                minLen = currentLen
            }
            sum -= nums[start]
            start++
        }
    }

    if minLen > len(nums) {
        return 0
    }

    return minLen
}