滑动窗口模板

滑动窗口属于双指针算法的一种, 适合解决子串问题(查找满足一定条件的连续区间的性质(如长度)的问题)。在滑动窗口算法中需要维护一个窗口,并让窗口在字符串上游走。具体实现时需要维护两个指针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
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 滑动窗口算法思想是非常重要的一种思想,可以用来解决数组,字符串的子元素问题。它可以将嵌套循环的问题,转换为单层循环...
    程序员will阅读 1,964评论 0 1
  • 读完本文,你可以去力扣拿下如下题目: 76.最小覆盖子串[https://leetcode-cn.com/prob...
    labuladong阅读 1,202评论 0 4
  • 本文来解决一类最难掌握的双指针技巧:滑动窗口技巧。总结出一套框架,可以保你闭着眼睛都能写出正确的解法。labula...
    _魔佃_阅读 276评论 0 0
  • 滑动窗口可以解决哪些问题? 76. 最小覆盖字串 567. 字符串的排列 438. 找到字符串中所有字...
    茹忆小玉儿阅读 4,103评论 0 3
  • 滑动窗口算法常与双指针等方法结合使用,常用于解决数组、字符串的子元素问题。维护头尾两个指针,头尾指针之间的部分就是...
    墨痕_UCAS阅读 286评论 0 2

友情链接更多精彩内容