209. Minimum Size Subarray Sum

Medium

Description

給定正整數陣列 nums 和正整數 target，回傳和 >= target 的最短連續子陣列長度。若不存在則回傳 0。

Example:

Input: target = 7, nums = [2,3,1,2,4,3] Output: 2（子陣列 [4,3] 和為 7）

Intuition#

核心思路：可變大小滑動視窗，右指針擴展累加總和，當總和 >= target 時嘗試收縮左邊界找最短長度。

所有元素為正數，所以視窗越大總和越大 – 單調性保證滑動視窗的正確性
右指針持續擴展，左指針在滿足條件時盡量收縮
每次滿足條件時更新最小長度

Approaches#

1: Brute Force#

概念: 嘗試所有起點，向右累加直到 >= target
時間複雜度: O(n²)
空間複雜度: O(1)

Brute Force 程式碼

class Solution {
    fun minSubArrayLen(target: Int, nums: IntArray): Int {
        var result = Int.MAX_VALUE
        for (i in nums.indices) {
            var sum = 0
            for (j in i until nums.size) {
                sum += nums[j]
                if (sum >= target) {
                    result = minOf(result, j - i + 1)
                    break
                }
            }
        }
        return if (result == Int.MAX_VALUE) 0 else result
    }
}

⭐2: Sliding Window（可變大小）#

概念: 維護視窗總和，右指針擴展、左指針收縮
時間複雜度: O(n) - 左右指針各最多遍歷 n 次
空間複雜度: O(1)

class Solution {
    fun minSubArrayLen(target: Int, nums: IntArray): Int {
        var left = 0
        var sum = 0
        var result = Int.MAX_VALUE

        for (right in nums.indices) {
            sum += nums[right]
            while (sum >= target) {
                result = minOf(result, right - left + 1)
                sum -= nums[left]
                left++
            }
        }
        return if (result == Int.MAX_VALUE) 0 else result
    }
}

此題元素全為正數才能用滑動視窗。若有負數，需要用 Prefix Sum + TreeMap 等方法。

🔑 Takeaways#

Pattern: 可變大小滑動視窗（找最短滿足條件的子陣列）
關鍵技巧: 當視窗滿足條件時用 while 持續收縮左邊界，確保找到最小長度；正數陣列的單調性是此方法的前提