首页 > 编程语言 > 详细

算法-滑动窗口

时间:2021-09-01 13:43:22      阅读:28      评论:0      收藏:0      [点我收藏+]

滑动窗口模式:

识别子串,子串中存在着重复的模式。

因为有重复的模式,所以窗口可以固定地向一个方向滑动,而不需要重新从头开始。

 

经典题目:

1. 无重复字符的最长子串

模式:如果某一个子串无重复字符,则窗口可以向前滑动一步进行判断,因为新的窗口-1内的字符必定不会重复。

即无重复字符的子串的子串,必定无重复字符。

解决:滑动窗口 X 双指针

左边的指针为起始点,右边的指针为判断点。如果重复,则左指针向前一部;如果不重复,则右指针向前一部。

此时左指针移动N次,右指针移动N次。时间复杂度O(N)

(PS:应该还有优化空间,如重复的话,判断左指针的重复点?)

 

算法-滑动窗口

原文:https://www.cnblogs.com/simpleminds/p/15203249.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!