滑动窗口模式:
识别子串,子串中存在着重复的模式。
因为有重复的模式,所以窗口可以固定地向一个方向滑动,而不需要重新从头开始。
经典题目:
1. 无重复字符的最长子串
模式:如果某一个子串无重复字符,则窗口可以向前滑动一步进行判断,因为新的窗口-1内的字符必定不会重复。
即无重复字符的子串的子串,必定无重复字符。
解决:滑动窗口 X 双指针
左边的指针为起始点,右边的指针为判断点。如果重复,则左指针向前一部;如果不重复,则右指针向前一部。
此时左指针移动N次,右指针移动N次。时间复杂度O(N)
(PS:应该还有优化空间,如重复的话,判断左指针的重复点?)