算法-滑动窗口

滑动窗口模式:

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

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

 

经典题目:

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

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

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

解决:滑动窗口 X 双指针

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

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

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

 

算法-滑动窗口

上一篇:使用idea将工具类打包使用


下一篇:DAY3 ECS训练营——SLB负载均衡实践