LeetCode 209 最小長度子數組：雙指針 O(n) 與前綴和二分 O(n log n) 雙解法完整實現

題目重述

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

解法一：雙指針滑動窗口 O(n) —— 推薦

int minSubArrayLen(int s, int* nums, int numsSize) {
    int sum = nums[0], head = 0, tail = 0;
    int minL = numsSize + 1; // 不可能的大值

    while (tail < numsSize) {
        if (tail - head + 1 < minL && sum >= s)
            minL = tail - head + 1;
        if (sum >= s)
            sum -= nums[head++];
        else
            sum += nums[++tail];
        if (head > tail) tail = head; // 保護
    }
    return minL == numsSize + 1 ? 0 : minL;
}

關鍵點

• head、tail 維護窗口 [head, tail]
• sum >= s 時嘗試縮小左邊界更新答案
• sum < s 時擴大右邊界
• 全正數保證單調性，雙指針各走一遍

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

適用於含負數情況 (本題全正數亦可)。

核心思想

1. 計算前綴和 Sum[i] = nums[0] + ... + nums[i-1]，Sum[0]=0，遞增
2. 對每個右端點 i (1..n)，需找最大 j < i 使 Sum[i] - Sum[j] ≥ s，即 Sum[j] ≤ Sum[i] - s
3. 因 Sum 遞增，可二分查找最後一個 ≤ target 的位置

完整實現

// 在非降序列中找最後一個 < target 的位置 (即 ≤ target-1)
int binarySearchLastLess(int l, int r, int target, int* nums) {
    if (l >= r) return -1;
    while (l < r - 1) {
        int m = l + ((r - l) >> 1);
        if (nums[m] < target) l = m;
        else r = m - 1;
    }
    if (nums[r] < target) return r;
    if (nums[l] < target) return l;
    return -1;
}

int minSubArrayLenBinary(int s, int* nums, int numsSize) {
    int* Sum = (int*)malloc(sizeof(int) * (numsSize + 1));
    Sum[0] = 0;
    for (int i = 1; i <= numsSize; ++i) Sum[i] = Sum[i-1] + nums[i-1];

    int minL = numsSize + 1;
    for (int i = 1; i <= numsSize; ++i) {
        if (Sum[i] >= s) {
            int pos = binarySearchLastLess(0, i, Sum[i] - s + 1, Sum);
            if (pos != -1 && i - pos < minL) minL = i - pos;
        }
    }
    free(Sum);
    return minL == numsSize + 1 ? 0 : minL;
}

複雜度對比

Java 版滑動窗口 (LeetCode 標準)

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

總結

滑動窗口是正數子數組和約束問題的「銀彈」，O(n) 時間 O(1) 空間，代碼極簡。前綴和二分作為通用備選，理解其將區間和轉化為前綴和差值、利用單調性二分的思想，對解決含負數變體 (如 LeetCode 862) 至關重要。