labuladong的算法秘籍-读书笔记-我写了首诗，把滑动窗口算法变成了默写题

滑动窗口

思路

1、使用双指针的左右指针技巧，初始化left=right=0，把索引左闭右开区间称为一个窗口

2、不断增大right指针扩大窗口[left, right),直到窗口中字符串符合要求

3、停止增加right，不断减少left缩小窗口[left,right)直到窗口中字符串不符合要求。每次增加left，更新结果

4、重复2和3，直到right到达字符串s的尽头

第二步在寻找可行解，第三步在优化可行解，最终找到最优解。

套模板，只需要思考以下几个问题：

1、什么时候应该移动 right 扩大窗口？窗口加入字符时，应该更新哪些数据？

2、什么时候窗口应该暂停扩大，开始移动 left 缩小窗口？从窗口移出字符时，应该更新哪些数据？

3、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

力扣76题 最小覆盖子串

什么时候移动right？

valid数值小于need的长度时。

窗口加入字符时，需要更新哪些数据？

如果该字符在need中，window中该字符出现次数加一。如果该字符出现次数等于need中的次数。valid加一

什么时候暂停扩大？

当valid数值等于need长度时

从窗口移除字符时，需要更新哪些数据？

如果该字符在need中，window中该字符出现次数减一。如果该字符出现次数等于need中的次数，valid减一

结果应该在扩大窗口时还是缩小窗口时进行更新？

在缩小窗口的时候更新数据

力扣567 字符串的排列

力扣438 找到字符串中所有字母异位词

力扣3 无重复字符的最长子串

1、什么时候应该扩大窗口？

2、什么时候应该缩小窗口？

3、什么时候应该更新答案？

遇到字串问题，首先考虑使用滑动窗口。

使用滑动窗口，使用模板，并考虑上述三个问题

代码请见知乎

https://zhuanlan.zhihu.com/p/602059336