大家好呀，我是帅蛋。
今天解决长度最小的子数组，滑动窗口解决的经典题目，之前做过一道用队列求滑动窗口最大值。
滑动窗口呢，一般就用在数组或者字符串上，我们先从字面上来认识一下滑动窗口：
- 滑动：窗口可以按照一定的方向移动。
- 窗口：窗口大小可以固定，也可以不固定，此时可以向外或者向内，扩容或者缩小窗口直至满足条件。
了解了这些，下面开始直接肝题。
LeetCode 209：长度最小的子数组
题意
给定含有 n 个正整数的数组和一个正整数 target：
找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度，若不存在，返回 0。
示例
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
提示
- 1 <= target <= 10^9
- 1 <= len(nums) <= 10^5
- 1 <= nums[i] <= 10^5
题目解析
中等难度题，但是知道了思路，代码难度几乎没有，属于中等难度中的菜鸡。
通常最开始想到的最简单的方法肯定是暴力查找。
遍历数组 nums，每次将一个下标的元素作为子数组的开始，接下来从下标 i 开始向后遍历，找到最小下标 j，使得从 nums[i] 到 nums[j] 的和 >= target，更新子数组的最小长度。
这种方式使用双重 for 循环，时间复杂度为 O(n²)，鉴于 nums 的最大长度为 10^5，显然不是好办法。
不过我无聊试了一下，在 LeetCode 上暴力法是可以 AC 的，不过执行时间看的我直嘬牙花子。
而这道题比较经典的解法就是滑动窗口。
滑动窗口，看起来名字挺高大上，有点唬人，但是禁不住细看。
在文章开头我大概介绍了滑动窗口是啥，这本质上和解决【LeetCode 29 有序数组的平方】里用的 left 和 right 双指针没啥区别，只不过动的更自如，left 和 right 之间的间隔可以忽大忽小。
知道了这些，那解题步骤就很明确了：
- 使用左右指针 left 和 right，left 和 right 之间的长度即为滑动窗口的大小（即连续数组的大小）。
- 如果滑动窗口内的值 sum >= target，维护连续数组最短长度，left 向右移动，缩小滑动窗口。
- 如果滑动窗口内的值 sum < target，则 right 向有移动，扩大滑动窗口。
楞看可能还是有点懵，下面我们来看图解。
图解
以 target = 7, nums = [2,3,1,2,4,3] 为例。
首先初始化 left 和 right 指针以及当前和sum、最小长度 min_len。
# 滑动窗口左右边界 left = right = 0 # 记录当前元素和 sum = 0 # 记录最短长度 min_len = float('inf')
第 1 步：
left = 0，right = 0，target = 7
sum = sum + nums[right] = 0 + 2 = 2
sum < target
right 指针向右移动，扩大窗口
sum += nums[right] while sum < s: right += 1
第 2 步：
- left = 0，right = 1，target = 7
- sum = sum + nums[right] = 2 + 3 = 5
- sum < target
- right 指针向右移动，扩大窗口
第 3 步：
- left = 0，right = 2，target = 7
- sum = sum + nums[right] = 5 + 1 = 6
- sum < target
- right 指针向右移动，扩大窗口
第 4 步：
- left = 0，right = 3，target = 7
- sum = sum + nums[right] = 6 + 2 = 8
- sum > target
- min_len = min(min_len, right - left +1) = min(inf, 4) = 4
- sum = sum - nums[left] = 8 - 2 = 6
- left 指针向右移动，缩小窗口
while sum >= s: # 取之前窗口长度和当前窗口长度最短的 min_len = min(min_len, right - left + 1) # 去掉左侧的数 sum -= nums[left] # 缩小窗口 left += 1
第 5 步：
- left = 1，right = 3，target = 7，sum = 6
- sum < target
- right 指针向右移动，扩大窗口
第 6 步：
- left = 1，right = 4，target = 7
- sum = sum + nums[right] = 6 + 4 = 10
- sum > target
- min_len = min(min_len, right - left +1) = min(4, 4) = 4
- sum = sum - nums[left] = 10 - 3 = 7
- left 指针向右移动，缩小窗口
第 7 步：
- left = 2，right = 4，target = 7，sum = 7
- sum >= target
- min_len = min(min_len, right - left +1) = min(4, 3) = 3
- sum = sum - nums[left] = 7 - 1 = 6
- left 指针向右移动，缩小窗口
第 8 步：
- left = 3，right = 4，target = 7，sum = 6
- sum < target
- right 指针向右移动，扩大窗口
第 9 步：
- left = 3，right = 5，target = 7
- sum = sum + nums[right] = 6 + 3 = 9
- sum > target
- min_len = min(min_len, right - left +1) = min(3, 3) = 3
- sum = sum - nums[left] = 9 - 2 = 7
- left 指针向右移动，缩小窗口
第 10 步：
- left = 4，right = 5，target = 7，sum = 7
- sum >= target
- min_len = min(min_len, right - left +1) = min(3, 2) = 2
- sum = sum - nums[left] = 7 - 4 = 3
- right 已遍历完数组，end
p
本题解 left 指针和 right 指针最多只遍历数组 1 次，所以时间复杂度为 O(n)。
只额外开了 2 个指针，空间复杂度为 O(1)。
代码实现
Python 代码实现
class Solution: def minSubArrayLen(self, s: int, nums: List[int]) -> int: if not nums: return 0 n = len(nums) # 滑动窗口左右边界 left = right = 0 # 记录当前元素和 sum = 0 # 记录最短长度 min_len = float('inf') while right < n: sum += nums[right] # 如果当前元素和 >= s while sum >= s: # 取之前窗口长度和当前窗口长度最短的 min_len = min(min_len, right - left + 1) # 去掉左侧的数 sum -= nums[left] # 缩小窗口 left += 1 right += 1 # 如果整个数组所有元素的和相加都 < s # 即不存在符合条件的子数组，返回 0 if min_len == float('inf'): return 0 else: return min_len
Java 代码实现
class Solution { public int minSubArrayLen(int s, int[] nums) { int left = 0; int sum = 0; int result = Integer.MAX_VALUE; for (int right = 0; right < nums.length; right++) { sum += nums[right]; while (sum >= s) { result = Math.min(result, right - left + 1); sum -= nums[left++]; } } return result == Integer.MAX_VALUE ? 0 : result; } }
图解长度最小的子数组到这就结束了，图解整的很详细，每一步怎么走的都做了说明。
不要夸，就是这么贴心，只要跟着走下来，保证妥妥看懂。
但看懂不是最终目的，要自己多做总结，这样才会在碰到类似题的时候游刃有余。
谈笑间，难题灰飞烟灭！大家加油。
还有别忘了帮我点赞 + 在看，么么哒。
我是蛋蛋，我们下次见！
