滑动窗口算法
滑动窗口算法名称
滑动窗口算法
场景
当遇到找出序列中连续子序列满足某些条件的问题的时候,可以使用滑动窗口. 序列包括:数组,字符串,List,链表等.
当我们遇到了求满足目标的连续子序列的时候,第一直觉适用滑动子窗口
解决方案
滑动窗口模板:
//创建双指针
int left= start;
int right= start;
//右指针移动
while(right < end){
将rank=right位置的数据添加到窗口中.
while(!窗口不合规){
// 判断是否满足条件,更新结果.
left++;
}
if(窗口满足最终条件){
更新最终结果.
刷新窗口.
}
right++;
}
返回结果.效果
满足某个要求的连续子串普通的实现至少是 O(n^2).但是适用滑动窗口能够将问题复杂度降低到 O(n).
实例
问题一 剑指 Offer II 008. 和大于等于 target 的最短子数组
给定一个含有n个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
给定一个含有n个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums =
输出：2
解释：子数组是该条件下的长度最小的子数组。
例 2：
输入：target = 4, nums =
输出：1
示例 3：
输入：target = 11, nums =
输出：0
<blockquote>
提示：
1
页:
[1]