doocs/leetcode 题解精讲:209. 长度最小的子数组——前缀和二分与滑动窗口双解法

原创2026-10-16 21:01:041,742 阅读
文章标签:教程示例工程教育

doocs/leetcode 题解精讲:209. 长度最小的子数组——前缀和二分与滑动窗口双解法

导读

本文以 doocs/leetcode 仓库中 0209.Minimum Size Subarray Sum 题解文档 为主体,系统讲解 LeetCode 209「长度最小的子数组」这道经典滑动窗口题目。文章完整覆盖题目约束、两种官方解法(前缀和 + 二分查找、双指针滑动窗口)的原理推导与 Python3 / Java / C++ / Go / TypeScript / Rust / C# 多语言实现,并补充溢出防护、边界判定等实现细节,帮助读者在面试与工程中自如套用这套"窗口维护"方法论。

题目速览:求最短的"和达标"连续子数组

给定一个含有 n 个正整数的数组 nums 和一个正整数 target,找出该数组中满足其总和大于等于 target 的长度最小的子数组 [nums_l, nums_{l+1}, ..., nums_{r-1}, nums_r],并返回其长度。如果不存在符合条件的子数组,返回 0。

示例

  • 示例 1:target = 7, nums = [2,3,1,2,4,3],输出 2。解释:子数组 [4,3] 是该条件下的长度最小的子数组。
  • 示例 2:target = 4, nums = [1,4,4],输出 1。单个元素 [4] 即可达标。
  • 示例 3:target = 11, nums = [1,1,1,1,1,1,1,1],输出 0。全数组之和也只有 8,无法达标。

约束与进阶

约束项 取值范围
target 1 <= target <= 10^9
nums.length 1 <= nums.length <= 10^5
nums[i] 1 <= nums[i] <= 10^4

进阶要求:如果你已经实现 O(n) 时间复杂度的解法,请尝试设计一个 O(n log(n)) 时间复杂度的解法。也就是说,官方希望读者至少掌握"滑动窗口"和"前缀和 + 二分查找"两条路线——本文接下来就逐一展开。

思路起点:为什么暴力枚举不可行

最直观的做法是枚举全部子数组并求和,复杂度为 O(n2)O(n^2),在 n <= 10^5 的数据规模下必然超时。

题目之所以能用更优解法,依赖一个关键前提:nums 中元素均为正整数。由此可以推出两条重要性质:

  1. 前缀和单调递增:记 s[i] 为前 i 项元素之和,则 s 严格单调递增,这为二分查找提供了有序性基础;
  2. 窗口和的单调性:窗口和随右端扩张而增大、随左端右移而减小,这为双指针滑动窗口提供了可行性。

这两条性质分别导出了本文的两种解法。

方法一:前缀和 + 二分查找(O(n log n))

原理推导

先预处理出数组 nums 的前缀和数组 s,其中 s[i] 表示数组 nums 前 i 项元素之和(s[0] = 0)。由于元素均为正整数,数组 s 单调递增。初始化答案 ans = n + 1,其中 n 为数组 nums 的长度。

接下来遍历前缀和数组 s:对于每个 s[i],子数组 nums[i..j-1] 的和等于 s[j] - s[i],要让它大于等于 target,等价于寻找满足:

s[j]≥s[i]+targets[j] \ge s[i] + \textit{target}

的最小下标 j。由于 s 单调递增,这一步可以直接用二分查找完成。若找到的 j <= n,说明存在满足条件的子数组,用 j - i 更新答案:ans = min(ans, j - i)。

最后,若 ans <= n,说明存在满足条件的子数组,返回 ans;否则返回 0。

复杂度:时间复杂度 O(n×log⁡n)O(n \times \log n),空间复杂度 O(n)O(n),其中 n 为数组长度。

各语言实现

Python3

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        s = list(accumulate(nums, initial=0))
        ans = n + 1
        for i, x in enumerate(s):
            j = bisect_left(s, x + target)
            if j <= n:
                ans = min(ans, j - i)
        return ans if ans <= n else 0

对应源码:Solution.py。这里 accumulate(nums, initial=0) 一行生成带 s[0]=0 的前缀和数组,bisect_left 正是求"第一个大于等于 x + target 的下标"的标准工具。

Java

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        long[] s = new long[n + 1];
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + nums[i];
        }
        int ans = n + 1;
        for (int i = 0; i <= n; ++i) {
            int j = search(s, s[i] + target);
            if (j <= n) {
                ans = Math.min(ans, j - i);
            }
        }
        return ans <= n ? ans : 0;
    }

    private int search(long[] nums, long x) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

对应源码:Solution.java。注意前缀和数组声明为 long[]:n 最大为 10^5、nums[i] 最大为 10^4,前缀和最大可达 10^9,接近 int 上限,用 long 可避免累加溢出。手写的 search 二分即 lower_bound 语义,返回第一个满足 nums[mid] >= x 的下标。

C++

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        vector<long long> s(n + 1);
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + nums[i];
        }
        int ans = n + 1;
        for (int i = 0; i <= n; ++i) {
            int j = lower_bound(s.begin(), s.end(), s[i] + target) - s.begin();
            if (j <= n) {
                ans = min(ans, j - i);
            }
        }
        return ans <= n ? ans : 0;
    }
};

C++ 版本直接复用 STL 的 lower_bound,前缀和同样选用 long long 防止溢出。

Go

func minSubArrayLen(target int, nums []int) int {
	n := len(nums)
	s := make([]int, n+1)
	for i, x := range nums {
		s[i+1] = s[i] + x
	}
	ans := n + 1
	for i, x := range s {
		j := sort.SearchInts(s, x+target)
		if j <= n {
			ans = min(ans, j-i)
		}
	}
	if ans == n+1 {
		return 0
	}
	return ans
}

Go 版本使用 sort.SearchInts 在有序切片上完成二分。这里以 ans == n+1 是否保持初始值来判断是否存在合法子数组。

TypeScript

function minSubArrayLen(target: number, nums: number[]): number {
    const n = nums.length;
    const s: number[] = new Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i) {
        s[i + 1] = s[i] + nums[i];
    }
    let ans = n + 1;
    const search = (x: number) => {
        let l = 0;
        let r = n + 1;
        while (l < r) {
            const mid = (l + r) >>> 1;
            if (s[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    };
    for (let i = 0; i <= n; ++i) {
        const j = search(s[i] + target);
        if (j <= n) {
            ans = Math.min(ans, j - i);
        }
    }
    return ans === n + 1 ? 0 : ans;
}

TypeScript 版本手写二分时用 >>> 1(无符号右移)计算 mid,避免 (l + r) 可能出现的负数或溢出问题,这是 JS/TS 语言中二分实现的常见细节。

方法二:双指针 / 滑动窗口(O(n))

原理推导

方法一仍需 O(n)O(n) 空间,且多出一个对数因子。由于元素均为正整数,窗口和随右端扩张而增大、随左端右移而减小,具有单调性,因此可以直接用双指针维护一个滑动窗口,把复杂度降到 O(n)O(n) 与 O(1)O(1)。

具体地,定义两个指针 l 和 r 分别表示滑动窗口的左、右边界,变量 s 代表窗口内元素之和:

  1. 每一步移动右指针 r,让窗口加入一个元素 nums[r];
  2. 若此时 s >= target,则用 r - l + 1 更新最小长度 ans;
  3. 然后循环右移左指针 l(同时从 s 中减去 nums[l]),直至 s < target,再进入下一轮扩张。

每个下标至多进出窗口一次,因此总复杂度为 O(n)O(n)。若最终 ans 仍为初始值,说明整个数组之和都不足 target,返回 0。

复杂度:时间复杂度 O(n)O(n),空间复杂度 O(1)O(1)。

各语言实现

Python3

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        l = s = 0
        ans = inf
        for r, x in enumerate(nums):
            s += x
            while s >= target:
                ans = min(ans, r - l + 1)
                s -= nums[l]
                l += 1
        return 0 if ans == inf else ans

对应源码:Solution2.py。这里用 inf(正无穷)作为初始值,最后以 ans == inf 判断是否无解。

Java

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int l = 0, n = nums.length;
        long s = 0;
        int ans = n + 1;
        for (int r = 0; r < n; ++r) {
            s += nums[r];
            while (s >= target) {
                ans = Math.min(ans, r - l + 1);
                s -= nums[l++];
            }
        }
        return ans > n ? 0 : ans;
    }
}

窗口和 s 同样用 long 承载:极端情况下窗口可能接近整个数组,和可达 10^9 量级,超出 int 安全范围。

C++

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int l = 0, n = nums.size();
        long long s = 0;
        int ans = n + 1;
        for (int r = 0; r < n; ++r) {
            s += nums[r];
            while (s >= target) {
                ans = min(ans, r - l + 1);
                s -= nums[l++];
            }
        }
        return ans > n ? 0 : ans;
    }
};

Go

func minSubArrayLen(target int, nums []int) int {
	l, n := 0, len(nums)
	s, ans := 0, n+1
	for r, x := range nums {
		s += x
		for s >= target {
			ans = min(ans, r-l+1)
			s -= nums[l]
			l++
		}
	}
	if ans > n {
		return 0
	}
	return ans
}

TypeScript

function minSubArrayLen(target: number, nums: number[]): number {
    const n = nums.length;
    let [s, ans] = [0, n + 1];
    for (let l = 0, r = 0; r < n; ++r) {
        s += nums[r];
        while (s >= target) {
            ans = Math.min(ans, r - l + 1);
            s -= nums[l++];
        }
    }
    return ans > n ? 0 : ans;
}

Rust

impl Solution {
    pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut res = n + 1;
        let mut sum = 0;
        let mut i = 0;
        for j in 0..n {
            sum += nums[j];

            while sum >= target {
                res = res.min(j - i + 1);
                sum -= nums[i];
                i += 1;
            }
        }
        if res == n + 1 {
            return 0;
        }
        res as i32
    }
}

对应源码:Solution.rs。需要说明的是,从源码结构看,本仓库的 Rust 解法直接采用了双指针实现(方法二),未单独提供前缀和二分的 Rust 版本;res 保持初始值 n + 1 即表示无解。

C#

public class Solution {
    public int MinSubArrayLen(int target, int[] nums) {
        int n = nums.Length;
        long s = 0;
        int ans = n + 1;
        for (int i = 0, j = 0; i < n; ++i) {
            s += nums[i];
            while (s >= target) {
                ans = Math.Min(ans, i - j + 1);
                s -= nums[j++];
            }
        }
        return ans == n + 1 ? 0 : ans;
    }
}

对应源码:Solution.cs。C# 版本以 i 为右边界、j 为左边界,写法与其余语言完全同构。

两种方法对比与实现要点

维度 方法一:前缀和 + 二分 方法二:双指针滑动窗口
时间复杂度 O(nlog⁡n)O(n \log n) O(n)O(n)
空间复杂度 O(n)O(n)(前缀和数组) O(1)O(1)
依赖前提 前缀和单调递增 窗口和随左右边界单调变化
典型适用 需要任意 s[i] 快速查询的场景,进阶要求路线 面试最推荐的在线性解法

实现层面的几个共性要点值得注意:

  • 答案初始值:ans 初始化为 n + 1(或 inf),因为理论上最长的合法子数组长度也不会超过 n,n + 1 天然充当"未更新"哨兵;
  • 无解判定:不同语言分别以 ans == n + 1、ans > n 或 ans == inf 判断,本质都是"哨兵值未被更新";
  • 防溢出:target 最大为 10^9,前缀和与窗口和需要 long / long long 承载,Java、C++、C# 源码均已体现这一点;
  • 二分边界:前缀和二分的查找区间是 [0, n],找到的下标 j 若等于 n 表示"恰好整个剩余数组达标",j > n 才意味着无解。

同源变体:剑指 Offer II 008(2VG8Kg)

值得关注的是,本题与《剑指 Offer(专项突破版)》中的 剑指 Offer II 008. 和大于等于 target 的最短子数组 是同一道题——该文档中明确注明"本题与主站 209 题相同"。两处题目描述、示例与约束完全一致(lcof2 版约束为 nums[i] <= 10^5),仓库为此也单独维护了一套题解目录。

lcof2 版本同样以双指针作为推荐解法,并额外提供了 Swift 实现,可作交叉参考:

class Solution {
    func minSubArrayLen(_ target: Int, _ nums: [Int]) -> Int {
        let inf = Int.max
        var ans = inf
        var sum = 0
        var i = 0

        for j in 0..<nums.count {
            sum += nums[j]
            while sum >= target {
                ans = min(ans, j - i + 1)
                sum -= nums[i]
                i += 1
            }
        }

        return ans == inf ? 0 : ans
    }
}

小结

LeetCode 209「长度最小的子数组」是理解"前缀和 + 二分"与"滑动窗口双指针"两套经典技巧的最佳入门题之一:

  • 正整数前提让前缀和单调、窗口和单调,分别支撑起两种解法的正确性;
  • 前缀和 + 二分(O(nlog⁡n)O(n \log n))满足题目进阶要求,空间换时间的思路可迁移到需要快速区间查询的题目;
  • 双指针滑动窗口(O(n)O(n))是面试最优解,每个元素最多进出窗口一次,常数空间、线性时间,务必熟练掌握其"先扩张、达标即收缩"的写法模板。

完整题解文档见 0209.Minimum Size Subarray Sum/README.md,全部多语言源码可直接在仓库对应目录下查看。

登录后查看全文
leetcode