滑動(dòng)窗口

思路

1、使用雙指針的左右指針技巧，初始化left=right=0，把索引左閉右開區(qū)間稱為一個(gè)窗口

2、不斷增大right指針擴(kuò)大窗口[left, right),直到窗口中字符串符合要求

3、停止增加right，不斷減少left縮小窗口[left,right)直到窗口中字符串不符合要求。每次增加left，更新結(jié)果

4、重復(fù)2和3，直到right到達(dá)字符串s的盡頭

第二步在尋找可行解，第三步在優(yōu)化可行解，最終找到最優(yōu)解。

套模板，只需要思考以下幾個(gè)問題：

1、什么時(shí)候應(yīng)該移動(dòng) right 擴(kuò)大窗口？窗口加入字符時(shí)，應(yīng)該更新哪些數(shù)據(jù)？

2、什么時(shí)候窗口應(yīng)該暫停擴(kuò)大，開始移動(dòng) left 縮小窗口？從窗口移出字符時(shí)，應(yīng)該更新哪些數(shù)據(jù)？

3、我們要的結(jié)果應(yīng)該在擴(kuò)大窗口時(shí)還是縮小窗口時(shí)進(jìn)行更新？

力扣76題 最小覆蓋子串

什么時(shí)候移動(dòng)right？

valid數(shù)值小于need的長度時(shí)。

窗口加入字符時(shí)，需要更新哪些數(shù)據(jù)？

如果該字符在need中，window中該字符出現(xiàn)次數(shù)加一。如果該字符出現(xiàn)次數(shù)等于need中的次數(shù)。valid加一

什么時(shí)候暫停擴(kuò)大？

當(dāng)valid數(shù)值等于need長度時(shí)

從窗口移除字符時(shí)，需要更新哪些數(shù)據(jù)？

如果該字符在need中，window中該字符出現(xiàn)次數(shù)減一。如果該字符出現(xiàn)次數(shù)等于need中的次數(shù)，valid減一

結(jié)果應(yīng)該在擴(kuò)大窗口時(shí)還是縮小窗口時(shí)進(jìn)行更新？

在縮小窗口的時(shí)候更新數(shù)據(jù)

力扣567 字符串的排列

力扣438 找到字符串中所有字母異位詞

力扣3 無重復(fù)字符的最長子串

1、什么時(shí)候應(yīng)該擴(kuò)大窗口？

2、什么時(shí)候應(yīng)該縮小窗口？

3、什么時(shí)候應(yīng)該更新答案？

遇到字串問題，首先考慮使用滑動(dòng)窗口。

使用滑動(dòng)窗口，使用模板，并考慮上述三個(gè)問題

代碼請(qǐng)見知乎

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