滑动窗口属于双指针算法的一种, 适合解决子串问题(查找满足一定条件的连续区间的性质(如长度)的问题)。在滑动窗口算法中需要维护一个窗口,并让窗口在字符串上游走。具体实现时需要维护两个指针l和r,表示滑动窗口的左边界和右边界,滑动窗口为左闭右开区间[l,r)。l和r初始化为0,此时滑动窗口长度为0。
滑动窗口要如何在字符串上移动呢?我们首先移动右指针r不断扩张窗口,移动到[l,r)滑动窗口内的元素满足题目要求。然后我们再移动左指针l收缩窗口,直到滑动区间不再符合题目要求。然后再继续移动r,...循环操作直到r到达字符串的终点。在这个过程中我们不断更新当前最优值。
我们可以得出,r指针用来延伸现有窗口,找到可行解;l指针用来收缩窗口,优化这个可行解。在滑动窗口游走的任意时刻,只有一个指针在移动,而另一个保持静止。随着左右指针不断前进,窗口不断向右滑动。
(1)l不动,向右移动r直到[l,r)窗口内刚好包含T中的所有字母。
(2)r不动,向右移动l使得[l,r)窗口不断缩小,更新最优解。直到窗口内字符串不再符合要求(并不包含T中的所有字母)。
(3)重复第1步和第2步,直到right = len(S)算法结束。
模板
left,right = 0,0
while right < len(s):
windows.append(s[right])
right += 1
while (windows needs shrink):
window.pop(0)
left += 1