什么是滑动窗口?
同向双指针
什么时候用滑动窗口?
利用带调性, 两个指针都不用回退的时候
怎么用?
- 初始化 left = 0; right= 0;
- 进窗口
- 判断是否出窗口
滑动窗口的正确性
利用单调性规避了很多没有必要的枚举行为
209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
算法思路
解法一: 暴力
最初看到这个题的时候, 很多人都会第一时间想到暴力枚举, 「从前往后」枚举数组中的任意⼀个元素，把它当成起始位置。然后从这个「起始位置」开始，然后寻找⼀段最短的区间，使得这段区间的和「⼤于等于」⽬标值。将所有元素作为起始位置所得的结果中，找到「最⼩值」即可。显而易见, 这是超时的.
解法二: 滑动窗口
由于此问题分析的对象是"⼀段连续的区间"，因此可以考虑滑动窗⼝的思想来解决这道题。
让滑动窗口满足, 从i位置开始, 窗口内所有元素的和小于target(那么当窗口内元素之和第一次大于等于目标值的时候, 就是从i位置开始, 满足条件的最小长度)
将有段元素划入窗口中, 统计出此时窗口内元素的和:
- 如果窗口内元素之和大于等于
target: 更新结果, 并且将左端元素划出去的同时, 继续判定是否满足条件并更新结果. - 如果窗口内元素之和不满足条件,
right++, 让下一个元素进入窗口.
public int minSubArrayLen(int target, int[] nums) {
int len = Integer.MAX_VALUE;
int sum = 0;
for(int right = 0, left = 0; right < nums.length; right++) {
sum += nums[right];//进窗口
while (sum >= target) {
len = Math.min(len, right - left + 1);//更新结果
sum -= nums[left++];//出窗口
}
}
return len == Integer.MAX_VALUE ? 0 : len;
}
