【滑动窗口】一题讲透滑动窗口！

🚀个人主页：一颗小谷粒

🚀所属专栏：力扣刷题

很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

目录

1.1 题目要求 

1.2 算法图解分析

1.3 代码实现

1.4 时间复杂度分析

1.5 算法思想总结

---

1.1 题目要求 

LeetCode.209 是一道非常经典的滑动窗口题目，题目如下：

209. 长度最小的子数组 - 力扣（LeetCode）

​

如果你不了解滑动窗口的话，那么只能通过暴力来解决，也就是通过两个for循环依次从左到右枚举，这么做的时间复杂度是O(n^2)，那么有没有更高效的方法呢？

通过滑动窗口动态地调整子数组的范围，快速找到最优解：

1.2 算法图解分析

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

分别定义子数组的左边界 left 和右边界 right ，依次枚举子数组的右端点，也就是right

​

此时 right = 0 ，子数组的元素和sum = 2，因为不满足sum >= target(7) ，所以继续右移右端点

​

 此时 right = 1 ，子数组的元素和sum = 5，因为不满足sum >= target(7) ，继续右移右端点

​

直到 right = 3 时 ，子数组的元素和sum = 8，满足sum >= target(7) ，这时我们首先要记录子数组的元素个数res，然后再向右移动左端点，也就是缩小子数组的左边界，再次判断缩小后的子数组元素和sum 是否满足sum >= target(7)。不满足移动右端点，满足则缩小左边界。

​

当缩小左边界后，子数组的元素和sum = 6，因为不满足sum >= target(7) ，所以继续枚举右端点

​

继续移动右端点后sum = 10 ， 满足sum >= target(7) ，这时我们记录子数组元素个数res，并继续向右移动左端点来缩小子数组的左边界，判断缩小后的子数组元素和sum 是否满足sum >= target(7)。不满足移动右端点，满足则缩小左边界。

​

缩小后sum = 7，依然满足 sum >= target(7)，我们继续上一步操作

​

 此时sum = 6，因为不满足sum >= target(7) ，所移继续右移右端点

​

sum = 9，缩小左端点

​

sum = 7 ，缩小左端点  

​

最后 sum = 3，由于右端点移动到了终点，此时跳出循环，返回结果为最小的res

1.3 代码实现

    public int minSubArrayLen(int target, int[] nums) {int n = nums.length;int res = n + 1;int sum = 0;int left = 0;//枚举子数组右边界for (int right = 0; right < n; right++) {sum = sum + nums[right];//缩小左边界while (sum - nums[left] >= target) {sum = sum - nums[left];left++;}if (sum >= target) {//保存子数组元素个数res = Math.min(res, right - left + 1);}}return res <= n ? res : 0;}

1.4 时间复杂度分析

子数组的右端点是从左到右枚举的，它是O(n)的，子数组的左端点是不断缩小的，它也是O(n)的；因此这个算法的时间复杂度就是O(n)的。

空间复杂度：O(1)。仅用到若干额外变量。

1.5 算法思想总结

1. 初始化窗口的左右边界，通常左边界和右边界都从数据结构的起始位置开始。
2. 不断地移动右边界来扩展窗口，直到窗口满足特定条件（例如包含了所有目标元素）。
3. 一旦满足条件，就尝试移动左边界来收缩窗口，同时保持条件仍然满足，目的是找到最小的满足条件的窗口大小或者窗口内容。
4. 在整个过程中，根据需要记录窗口的状态、大小、元素等信息

---

---

刷题总是枯燥痛苦的，但是各位，计算机人是不怕吃苦的，万事开头难，不是看到了希望才去坚持，而是坚持了才有希望！最后由衷地祝愿所有的计算机人在学习的路上一路顺风，我们顶峰相见！博主微信：g2279605572