滑动窗口算法

打印 上一主题 下一主题

主题 781|帖子 781|积分 2343

滑动窗口算法

名称

滑动窗口算法
场景

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

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

满足某个要求的连续子串普通的实现至少是 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
回复

使用道具 举报

0 个回复

倒序浏览

快速回复

您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

羊蹓狼

金牌会员
这个人很懒什么都没写!

标签云

快速回复 返回顶部 返回列表