209. Minimum Size Subarray Sum

題目 / Problem

給定一個由正整數組成的陣列 nums，以及一個正整數 target。請回傳「總和大於或等於 target」的連續子陣列中，長度最短的那一個的長度。如果不存在這樣的子陣列，回傳 0。

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

約束 / Constraints - 1 <= target <= 10^9 - 1 <= nums.length <= 10^5 - 1 <= nums[i] <= 10^4

範例 / Worked example - Input: target = 7, nums = [2,3,1,2,4,3] - Output: 2 - 說明：子陣列 [4,3] 的總和是 7 >= 7，長度為 2，是所有合格子陣列中最短的。/ The subarray [4,3] sums to 7 >= 7 and has length 2, which is the shortest among all qualifying subarrays.

名詞解釋 / Glossary

• 子陣列 / Subarray：陣列中連續的一段元素（中間不能跳過）。例如 [2,3,1] 是 [2,3,1,2,4,3] 的子陣列，但 [2,1,3] 不是（因為不連續）。/ A contiguous slice of the array — you cannot skip elements in the middle.
• 滑動視窗 / Sliding window：用兩個索引 left 和 right 框住一段連續區間，像一個會伸縮的「窗口」。右端往右擴張以納入更多元素，左端往右收縮以踢掉元素，從而在 O(n) 時間內檢查所有可能的連續區間。/ A pair of indices left and right bounding a contiguous range; expand on the right to include elements, shrink on the left to drop them.
• 雙指針 / Two pointers：用兩個整數索引（這裡是 left、right）在陣列上移動，而不是用巢狀迴圈逐一比對，藉此降低時間複雜度。/ Two integer indices walking across the array instead of nested loops.
• 不變量 / Invariant：在演算法每一步都保持為真的條件。本題的關鍵不變量是「視窗一旦總和 >= target，就盡量從左邊收縮到不能再收」。/ A condition kept true at every step; here: whenever the window sum reaches target, we shrink from the left as much as possible.
• 前綴和 / Prefix sum：prefix[i] 表示前 i 個元素的總和；任一子陣列 [l, r] 的總和可用 prefix[r+1] - prefix[l] 快速求得。本題的 O(n log n) 解法會用到它。/ prefix[i] is the sum of the first i elements; a subarray sum becomes a subtraction.
• 二分搜尋 / Binary search：在一個已排序的序列上，每次砍掉一半的搜尋範圍來快速定位目標，時間 O(log n)。因為所有數都是正的，前綴和陣列是嚴格遞增（已排序）的，所以可用二分搜尋。/ Repeatedly halving a sorted range to locate a value in O(log n).

思路

最直覺的暴力法是列舉所有子陣列：用兩層迴圈固定起點和終點，算出每段的總和，再記錄總和 >= target 的最短長度。但子陣列數量是 O(n²)，每段再算總和最壞又是 O(n)，總共 O(n³)（即使邊走邊累加總和也是 O(n²)），在 n 達到 10^5 時會超時。關鍵觀察是：所有數字都是正整數。這代表當視窗向右擴張時總和只會變大、向左收縮時只會變小，具有單調性。於是我們可以用滑動視窗：維持一個 [left, right] 區間和它的總和 sum。每次把 right 指到的新元素加進 sum，只要 sum >= target，就代表目前視窗合格——此時不要急著繼續擴張，而是反過來盡量把 left 往右收縮，每收縮一步就嘗試更新答案，直到 sum 掉到 target 以下為止。為什麼這樣能找到最短？因為對於每一個右端點，我們都把左端推到「再推一步就不合格」的極限位置，這保證了以該右端點結尾的最短合格視窗一定被檢查到；而每個元素最多被 right 加入一次、被 left 移除一次，所以總共只走 2n 步，時間是 O(n)。若全部走完都沒出現過合格視窗，答案就是 0。

The brute-force idea is to enumerate every subarray with two nested loops, summing each one and tracking the shortest whose sum reaches target. That is O(n²) subarrays (O(n³) naively, O(n²) even with running sums), which times out when n is up to 10^5. The decisive fact is that every number is a positive integer: extending the window on the right can only increase the sum, and shrinking it on the left can only decrease it — the sum moves monotonically. That lets us use a sliding window. Keep a range [left, right] and its running sum. Add each new right element to sum; the moment sum >= target, the window qualifies, so instead of growing further we shrink left rightward as far as possible, updating the answer at each shrink step, until sum drops back below target. This finds the minimum because for every right endpoint we push left to the tightest position that still qualifies, guaranteeing the shortest valid window ending at that point is examined. Each element is added by right once and removed by left once — about 2n moves total — so the whole thing is O(n). If no qualifying window ever appears, we return 0.

逐步走查 / Walkthrough

以 target = 7, nums = [2,3,1,2,4,3] 為例。初始 left = 0, sum = 0, ans = ∞（用一個很大的數代表「尚未找到」）。

We trace target = 7, nums = [2,3,1,2,4,3]. Start with left = 0, sum = 0, ans = ∞.

走訪結束，ans = 2，對應子陣列 [4,3]。/ The loop ends with ans = 2, the subarray [4,3].

Solution — C

// 滑動視窗法 / Sliding-window approach:
// 右指針 right 擴張視窗並累加總和；一旦總和 >= target，
// 就盡量收縮左指針 left 以求最短視窗，邊收縮邊更新答案。
// right expands the window and grows the sum; once sum >= target,
// shrink left as far as possible to minimize length, updating the answer.
#include <limits.h>   // 提供 INT_MAX 常數 / provides the INT_MAX constant

int minSubArrayLen(int target, int* nums, int numsSize) {
    long sum = 0;        // 當前視窗總和；用 long 避免最壞情況累加溢位 / current window sum; long avoids overflow
    int left = 0;        // 視窗左端索引 / left edge index of the window
    int ans = INT_MAX;   // 目前找到的最短長度，INT_MAX 代表「還沒找到」/ best length so far; INT_MAX means "none yet"

    // right 從 0 掃到尾，逐一把元素納入視窗右端 / move right across the array, adding each element
    for (int right = 0; right < numsSize; right++) {
        sum += nums[right];   // 把新元素加入視窗總和 / include the new element in the window sum

        // 只要視窗合格，就持續從左邊收縮 / while the window qualifies, keep shrinking from the left
        while (sum >= target) {
            int len = right - left + 1;   // 當前視窗長度（含兩端，故 +1）/ current window length, inclusive so +1
            if (len < ans) ans = len;     // 更新最短長度 / record a shorter window if found
            sum -= nums[left];            // 移除最左元素，準備縮小視窗 / drop the leftmost element
            left++;                       // 左端右移一格 / advance the left edge
        }
    }

    // 若 ans 從未被更新，表示無合格子陣列，依題意回傳 0 / if never updated, no valid subarray exists → return 0
    return ans == INT_MAX ? 0 : ans;
}

Solution — C++

// 滑動視窗法 / Sliding-window approach:
// right 擴張視窗並累加 sum；當 sum >= target 時收縮 left 取最短長度。
// 因為元素皆為正數，sum 隨視窗大小單調變化，每個元素至多進出視窗一次，故為 O(n)。
// right grows the window; left shrinks it when sum >= target. All-positive values
// make sum monotonic, so each element enters/leaves once → O(n).
#include <vector>
#include <climits>     // 提供 INT_MAX / provides INT_MAX
using namespace std;

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        long sum = 0;                 // 當前視窗總和，用 long 防溢位 / running window sum, long to avoid overflow
        int left = 0;                 // 視窗左端索引 / left edge of the window
        int ans = INT_MAX;            // 最短長度，初始為「無限大」/ best length, initialized to "infinity"
        int n = nums.size();          // size() 回傳容器元素個數 / size() returns the element count

        // 範圍以外用傳統索引迴圈，方便同時用 left/right 計算長度 / index loop so we can compute length from left/right
        for (int right = 0; right < n; ++right) {
            sum += nums[right];       // 將右端新元素併入總和 / add the element at right into the sum

            // 視窗合格時不斷收縮左端 / shrink the left edge while the window still qualifies
            while (sum >= target) {
                ans = min(ans, right - left + 1);  // min 取較小者，更新最短長度 / min keeps the smaller length
                sum -= nums[left];                 // 移除最左元素 / remove the leftmost element
                ++left;                            // 左端右移 / move the left edge rightward
            }
        }

        // 三元運算子：沒找到就回傳 0 / ternary: return 0 when no window was ever valid
        return ans == INT_MAX ? 0 : ans;
    }
};

複雜度 / Complexity

• Time: O(n) — right 從頭走到尾共 n 步；left 只會往右移動，整個過程最多移動 n 步，永不回頭。因此兩個指針合計約 2n 次操作，與 n 成線性關係（n 是陣列長度）。/ right advances n times; left only ever moves rightward, at most n times total, never backtracking — so the two pointers together do about 2n operations, linear in the array length n.
• Space: O(1) — 只用了 sum、left、ans 等少數固定變數，沒有隨輸入大小增長的額外結構。/ Only a handful of scalar variables (sum, left, ans); no extra structure that grows with the input.

Pitfalls & Edge Cases

• 整數溢位 / Integer overflow：最壞情況 sum 可達 10^5 × 10^4 = 10^9，雖然剛好落在 32 位 int 範圍內，但若不小心多累加幾步就可能溢出。用 long 累加是最安全的做法，避免未定義行為。/ The running sum can reach ~10^9; using long removes any risk of overflow.
• 不存在合格子陣列要回傳 0，不是回傳「無限大」/ No valid subarray → return 0, not the sentinel：用 INT_MAX 當哨兵代表「尚未找到」，結束時若 ans 仍是 INT_MAX，必須轉成 0。忘了這步會回傳一個巨大的錯誤值（如 Example 3）。/ If ans is still INT_MAX at the end (e.g. Example 3), convert it to 0.
• 視窗長度的 +1（off-by-one）/ Off-by-one in window length：長度是 right - left + 1，因為兩端索引都包含在內。漏掉 +1 會讓答案少 1。/ Length is right - left + 1 because both endpoints are included; dropping the +1 undercounts by one.
• 用 while 而非 if 收縮 / Shrink with while, not if：一次納入新元素後，可能需要連續收縮多步左端才會跌破 target（見走查 right=4、5 步驟）。若寫成 if 只收縮一次，會錯過更短的視窗。/ One new element may allow several left-shrinks; an if would shrink only once and miss shorter windows.
• 依賴「全為正數」的前提 / Relies on all-positive values：滑動視窗的正確性建立在「加元素總和變大、移元素總和變小」的單調性上。若陣列含 0 或負數，這個方法不再成立，需改用前綴和等其他技巧。/ The monotonicity (and thus this technique) breaks if zeros or negatives are present.