LeetCode 209 長度最小的子數組：雙指針滑動窗口 O(n) 解法

題目描述

給定正整數數組 nums 和目標值 s，找出總和 ≥ s 的連續子數組的最小長度。不存在返回 0。

示例：nums = [2,3,1,2,4,3], s = 7 → 子數組 [4,3] 長度 2 為最小。

核心思想：滑動窗口 (雙指針)

因所有數為正數，窗口擴大時和單調遞增，縮小時單調遞減。維護窗口 [left, right] 使其和 ≥ s，不斷嘗試縮小左邊界更新答案。

算法流程

1. left = 0, sum = 0, minLen = INF
2. 遍歷 right = 0 .. n-1：
   • sum += nums[right]
   • 當 sum >= s 時：
     • 更新 minLen = min(minLen, right - left + 1)
     • sum -= nums[left++] (縮小左邊界)
3. 返回 minLen == INF ? 0 : minLen

完整代碼

Java 版

public int minSubArrayLen(int s, int[] nums) {
    int n = nums.length;
    int left = 0, sum = 0;
    int minLen = n + 1; // 不可能超過 n

    for (int right = 0; right < n; ++right) {
        sum += nums[right];
        while (sum >= s) {
            minLen = Math.min(minLen, right - left + 1);
            sum -= nums[left++];
        }
    }
    return minLen == n + 1 ? 0 : minLen;
}

C++ 版

int minSubArrayLen(int s, vector& nums) {
    int n = nums.size();
    int left = 0, sum = 0;
    int minLen = n + 1;

    for (int right = 0; right < n; ++right) {
        sum += nums[right];
        while (sum >= s) {
            minLen = min(minLen, right - left + 1);
            sum -= nums[left++];
        }
    }
    return minLen == n + 1 ? 0 : minLen;
}

複雜度分析

• 時間：O(n) —— left 和 right 各自單調遞增，最多各走 n 步
• 空間：O(1)

進階：O(n log n) 解法 (前綴和 + 二分)

若數組含負數，滑動窗口失效。但本題全正數，仍可展示另一思路：

1. 計算前綴和 pre[i] = sum(nums[0..i-1])，pre[0]=0，遞增
2. 對每個 i，二分查找最大 j ≤ i 使 pre[i] - pre[j] ≥ s，即 pre[j] ≤ pre[i] - s
3. 長度 i - j，取最小

int minSubArrayLenBinary(int s, vector& nums) {
    int n = nums.size();
    vector pre(n + 1, 0);
    for (int i = 1; i <= n; ++i) pre[i] = pre[i-1] + nums[i-1];

    int minLen = n + 1;
    for (int i = 1; i <= n; ++i) {
        int target = pre[i] - s;
        // 找最後一個 ≤ target 的位置
        int j = upper_bound(pre.begin(), pre.begin() + i, target) - pre.begin() - 1;
        if (j >= 0) minLen = min(minLen, i - j);
    }
    return minLen == n + 1 ? 0 : minLen;
}

對比總結

相關題目

• LeetCode 862 和至少為 K 的最短子數組 (含負數，單調隊列 O(n))
• LeetCode 713 乘積小於 K 的子數組 (滑動窗口變體)
• LeetCode 904 水果成籃 (滑動窗口雙指針)

滑動窗口是處理「正數數組子區間和/積約束」的利器，掌握其單調性依賴與雙指針協同移動模式，可秒殺大批同類題目。