[LeetCode 解題紀錄] 209. Minimum Size Subarray Sum

209. Minimum Size Subarray Sum

https://leetcode.com/problems/minimum-size-subarray-sum/description/

Problem:

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Constraints:

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 104

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

題意

給定一個含有 n 個正整數的陣列 nums 和一個正整數 target。 請找出該陣列中滿足元素總和大於等於 target 的「長度最小」的連續子陣列，並返回其長度。如果不存在符合條件的子陣列，請返回 0。

問題解析

首先，看到題目我們可以先挑出關鍵字：重點：

• 正整數
• 「長度最小」的「連續」子陣列
• 最後要 return 長度

也就是要把子陣列加總後，找出最短且符合總和大於等於 target 的情況。

解法

暴力法 -> Sliding Window

先從暴力法思考，最直覺就是加總所有可能性的子陣列，從這個方向出發，可以發現如果加總全部可能的話，其實中間有許多操作是重複做好幾次的。

如果我們是一個可變動的視窗，發現加總不夠 target 的時候，就往右補一個進來，發現超過 target 的時候，除了紀錄當下的視窗長度外，同時也不斷的縮小，直到符合條件，再繼續往右補。

• 定義狀態：一個變數 currentSum 來記錄當前視窗內的數字總和。
• right：外層迴圈往右擴張，每次都把 nums[right] 加進 currentSum 裡。
• left：當 currentSum >= target 時，代表條件滿足，這時候進入 while 迴圈來吐出先前的值。

function minSubArrayLen(target: number, nums: number[]): number {
    const len = nums.length;
    let minLength = Infinity;

    // base case
    if (len === 0) return 0;

    let left = 0;
    let currentSum = 0;

    // 1. 外層迴圈往右擴張
    for (let right = 0; right < len; right++) {
        currentSum += nums[right];

        // 2. 當 currentSum >= target 時，代表條件滿足
        // 只要大於等於，就立刻進入 while 準備記錄並收縮
        while (currentSum >= target) {
            // 檢查更新最短長度
            minLength = Math.min(minLength, right - left + 1);

            // 記錄完之後，才把左邊的元素吐出來，試圖尋找更短的可能
            currentSum -= nums[left];
            left++;
        }
    }

    // 最後檢查：如果 minLength 還是 Infinity，代表從頭到尾都沒找到合法的
    return minLength === Infinity ? 0 : minLength;
};

讓我們先來 Dry run 一次

/*
target = 7, nums = [2, 3, 1, 2, 4, 3]
*/

// --- 開始向右擴張 ---
minLength=Infinity
[2, 3, 1, 2, 4, 3]
 l
 r
currentSum=2 (小於 7，繼續擴張)

minLength=Infinity
[2, 3, 1, 2, 4, 3]
 l
    r
currentSum=5 (小於 7，繼續擴張)

minLength=Infinity
[2, 3, 1, 2, 4, 3]
 l
       r
currentSum=6 (小於 7，繼續擴張)

// --- 第一次觸發收縮條件 ---
minLength=Infinity
[2, 3, 1, 2, 4, 3]
 l
          r
currentSum=8 (大於等於 7，觸發 while 迴圈)
// 【記錄】更新 minLength = min(Infinity, 4) = 4
// 【吐出】減去 nums[l] 的 2，l 往前

minLength=4
[2, 3, 1, 2, 4, 3]
    l
          r
currentSum=6 (小於 7，跳出 while，r 繼續擴張)

// --- 再次擴張並觸發收縮 ---
minLength=4
[2, 3, 1, 2, 4, 3]
    l
             r
currentSum=10 (大於等於 7，觸發 while 迴圈)
// 【記錄】更新 minLength = min(4, 4) = 4
// 【吐出】減去 nums[l] 的 3，l 往前

minLength=4
[2, 3, 1, 2, 4, 3]
       l
             r
currentSum=7 (大於等於 7，繼續在 while 迴圈內)
// 【記錄】更新 minLength = min(4, 3) = 3
// 【吐出】減去 nums[l] 的 1，l 往前

minLength=3
[2, 3, 1, 2, 4, 3]
          l
             r
currentSum=6 (小於 7，跳出 while，r 繼續擴張)

// --- 最後一次擴張與連續收縮 ---
minLength=3
[2, 3, 1, 2, 4, 3]
          l
                r
currentSum=9 (大於等於 7，觸發 while 迴圈)
// 【記錄】更新 minLength = min(3, 3) = 3
// 【吐出】減去 nums[l] 的 2，l 往前

minLength=3
[2, 3, 1, 2, 4, 3]
             l
                r
currentSum=7 (大於等於 7，繼續在 while 迴圈內)
// 【記錄】更新 minLength = min(3, 2) = 2  <-- 找到最佳解
// 【吐出】減去 nums[l] 的 4，l 往前

minLength=2
[2, 3, 1, 2, 4, 3]
                l
                r
currentSum=3 (小於 7，跳出 while)

// r 走到底，迴圈結束。
// 最終回傳 minLength = 2

時間複雜度：O(N)

• 雖然我們是兩層迴圈，但我們要看的是指標移動的總次數，外層的 right 指標從陣列最左邊走到最右邊，總共走了 N 步。 內層的 left 指標雖然在 while 裡面，但它只會前進，不會後退，所以它最多也是從最左邊走到最右邊，總共最多走 N 步，也就是說陣列中的每一個數字，最多只會被 right 吃進去 1 次，並且最多被 left 吐出來 1 次。 總操作次數大約是 2N，忽略常數後，時間複雜度就是 O(N)

空間複雜度：O(1)

更多演算法與資料結構文章：

[embed]基礎演算法與資料結構學習筆記 基礎演算法與資料結構，常常是工作後沒在用就很容易忘記，但面試又很愛考，每次要準備面試前都要重新搜集資料複習，這次就趁有時間時候，一邊複習一邊紀錄一下這次基礎演算法與資料結構的學習筆記。medium.com

[embed]