LeetCode 209：長度最小的子數組——前綴和+二分查找 vs 雙指針滑動窗口

題目回顧

給定一個正整數數組 nums 和目標值 s，找出該數組中滿足其和 ≥ s 的長度最小的連續子數組，並返回其長度。若不存在，返回 0。

解法一：前綴和 + 二分查找 — O(n log n)

核心思想

構建前綴和陣列 sum[i] = nums[0] + ... + nums[i-1]（sum[0]=0）。因全為正數，sum 嚴格遞增。對於每個右端點 i，需找最小的 j ≤ i 使 sum[i] - sum[j] ≥ s，即 sum[j] ≤ sum[i] - s。因 sum 有序，可二分查找最大的符合條件的 j（或用 upper_bound 找第一個 > sum[i]-s 的位置）。

關鍵代碼

int minSubArrayLen(int s, vector& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    vector sum(n + 1, 0);
    for (int i = 1; i <= n; ++i) sum[i] = sum[i-1] + nums[i-1];
    int ans = INT_MAX;
    for (int i = 1; i <= n; ++i) {
        int target = sum[i] - s;
        // 找最大的 j 使 sum[j] <= target
        auto it = upper_bound(sum.begin(), sum.begin() + i, target);
        if (it != sum.begin()) {
            int j = (it - sum.begin()) - 1;
            ans = min(ans, i - j);
        }
    }
    return ans == INT_MAX ? 0 : ans;
}

解法二：雙指針滑動窗口 — O(n) 最優

核心思想

維護一個滑動窗口 [left, right]，擴展 right 累加和直到 ≥ s，嘗試縮小 left 更新最小長度。因全為正數，縮小左邊界必減小和，故單調性保證 O(n)。

關鍵代碼

int minSubArrayLen(int s, vector& nums) {
    int n = nums.size();
    int left = 0, sum = 0, ans = INT_MAX;
    for (int right = 0; right < n; ++right) {
        sum += nums[right];
        while (sum >= s) {
            ans = min(ans, right - left + 1);
            sum -= nums[left++];
        }
    }
    return ans == INT_MAX ? 0 : ans;
}

複雜度對比

關鍵點總結

• 正數性質：滑動窗口依賴「增加元素增大和，移除元素減小和」的單調性。
• 邊界處理：初始 ans 設為 INT_MAX，最終判斷是否更新過。
• 變體擴展：若數組含負數，需用前綴和+單調隊列（LeetCode 862）。

總結

LeetCode 209 是滑動窗口的教科書級例題。掌握「前綴和+二分」作為通用基礎，理解「滑動窗口」在正數數組上的極致優化，是解決子數組和問題的核心功力。