滑动窗口算法

滑动窗口算法

名称

滑动窗口算法
场景

当遇到找出序列中连续子序列满足某些条件的问题的时候,可以使用滑动窗口. 序列包括:数组,字符串,List,链表等.
当我们遇到了求满足目标的连续子序列的时候,第一直觉适用滑动子窗口
解决方案

滑动窗口模板:

1. //创建双指针
2. int left= start;
3. int right= start;
5. //右指针移动
6. while(right < end){
8. 将rank=right位置的数据添加到窗口中.
10. while(!窗口不合规){
11.   // 判断是否满足条件,更新结果.
12.     left++;
13. }
15. if(窗口满足最终条件){
16.    更新最终结果.
17.    刷新窗口.
18. }
19. right++;
20.   
21. }
23. 返回结果.

复制代码

效果

满足某个要求的连续子串普通的实现至少是 O(n^2).但是适用滑动窗口能够将问题复杂度降低到 O(n).
实例

问题一 剑指 Offer II 008. 和大于等于 target 的最短子数组

给定一个含有n个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
给定一个含有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

<blockquote>
提示：
1