当前位置：首页 > news >正文

9.LeetCode 209. 长度最小的子数组 | 滑动窗口专题详解

news 2026/5/28 15:11:35

1. 题目解析

示例 1：

示例 2：

2. 算法原理

解法一：暴力枚举所有子数组的和 —— O(n²)

解法二：利用单调性，使用“同向双指针”来优化 —— O(n)

✅ 怎么用？

图解过程：

正确性？

时间复杂度

3. 编写代码

OJ链接： https://leetcode.cn/problems/minimum-size-subarray-sum/description/

1. 题目解析

本题来自 LeetCode 第 209 题：长度最小的子数组。

题目描述：
给定一个含有n个正整数的数组和一个正整数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

📌关键点：

子数组必须是连续的
要求和≥ target
返回的是最小长度，不是子数组本身
若不存在，返回0

2. 算法原理

解法一：暴力枚举所有子数组的和 —— O(n²)

通过双重循环枚举所有子数组，计算和并比较，时间复杂度为 O(n²)，在数据规模大时会超时。

解法二：利用单调性，使用“同向双指针”来优化 —— O(n)

这是本题的核心解法：滑动窗口（Sliding Window）

✅ 怎么用？

我们用两个指针left和right构建一个窗口，窗口内的元素和记为sum，窗口长度记为len。

步骤如下：

初始化：left = 0,right = 0
进窗口 →right向右移动，将nums[right]加入sum
判断 → 如果sum >= target，说明当前窗口满足条件，尝试缩小窗口
- 更新最小长度：len = min(len, right - left + 1)
- 出窗口 →left向右移动，sum -= nums[left++]
重复步骤 2~3，直到right遍历完整个数组

图解过程：

以target = 7, nums = [2,3,1,2,4,3]为例：

初始：left=0, right=0, sum=0, len=+∞
right=0→ 进窗口：sum=2→ 不满足
right=1→ 进窗口：sum=5→ 不满足
right=2→ 进窗口：sum=6→ 不满足
right=3→ 进窗口：sum=8→ 满足！→ 更新len=4，出窗口：sum=6, left=1
right=4→ 进窗口：sum=10→ 满足！→ 更新len=4（当前窗口 [3,1,2,4]），出窗口：sum=8, left=2
right=5→ 进窗口：sum=11→ 满足！→ 更新len=3（[1,2,4]），出窗口：sum=7, left=3
right=5→ 再次判断：sum=7 >=7→ 更新len=2（[2,4]），出窗口：sum=3, left=4
循环结束

✅ 最终最小长度为2

正确性？

利用单调性，规避了很多没有必要的枚举行为

因为数组元素都是正整数，所以当sum >= target时，我们移动left指针一定能缩小窗口，且不会错过更优解。这是滑动窗口能成立的核心前提。

时间复杂度

right指针遍历数组一次 → O(n)
left指针也最多移动 n 次 → O(n)
总体：O(n)

✅ 从 n+n → 2n → O(n)，线性时间复杂度，非常高效！

3. 编写代码

以下是 Java 实现代码

class Solution { public int minSubArrayLen(int target, int[] nums) { int n = nums.length, sum = 0, len = Integer.MAX_VALUE; for (int left = 0, right = 0; right < n; right++) { sum += nums[right]; // 进窗口 while (sum >= target) { // 判断 len = Math.min(len, right - left + 1); // 更新结果 sum -= nums[left++]; // 出窗口 } } return len == Integer.MAX_VALUE ? 0 : len; } }

可直接复制运行。

欢迎在评论区留言交流，我们一起把滑动窗口吃透！