Sliding Window

滑動窗口

概念

? 滑動窗口簡單來講就是一個子序列在主序列上滑動的一個過程，這個子序列滿足某種條件。

??它是動態(tài)規(guī)劃問題的一個子集，主要用在解決數(shù)組或鏈表上的問題，常常涉及到求最長/最短子序列。

? 一個窗口有左右兩個指針（left，right），兩個指針以一前一后的速度前進(jìn)，當(dāng)滿足某種條件的時候停止算法。

如何判斷一個問題是滑動窗口問題？

? 我們可以通過一些簡單的特征來判斷一個問題是否可以使用滑動窗口來解答：

• 該問題的數(shù)據(jù)結(jié)構(gòu)是數(shù)組/字符串類型，且是可迭代的。

• 該問題要求解出該數(shù)組/字符串的某個最長/最短子序列，或某個目標(biāo)值。

• 該問題能夠用簡單的暴力解法來解答，時間復(fù)雜度往往O（n2）以上。

? 最顯著的特征是，題目要求的往往是某種最優(yōu)的答案，比如滿足給定條件的最長的序列或最短的序列。

? 滑動窗口的優(yōu)勢在于，它的時間復(fù)雜度往往是O（n），空間復(fù)雜度O（1）。

參考模板

? 這是一個簡單的模板，它很好的歸納出了滑動窗口核心思想：

leetcode題目

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

分析：這是比較典型的求解字符串規(guī)定條件的子串問題。

首先，題目要求不含重復(fù)字符的最長子串，也就是說我們需要有一個條件用來判斷當(dāng)前字符是否在子串中出現(xiàn)過。我們這里可以通過哈希表來實現(xiàn)該判斷條件。

其次，我們觀察發(fā)現(xiàn)，當(dāng)一個位置(right)出現(xiàn)重復(fù)字符的時候，我們只需要從那個被重復(fù)的字符的位置重新開始計算即可，也就是把左指針 left 設(shè)置為那個字符的索引，之前的全部字符都可以拋棄掉。

核心部分：

• 哈希表? ? ? ?---->? ? ? 判斷當(dāng)前字符是否在前面出現(xiàn)過，存儲字符的索引

• 最長子串長度 =?當(dāng)前字符索引（right）?-?子串起始索引（left）?

• 確定邊界問題? ?---->? ?連續(xù)相同字符、當(dāng)前字符為初始字符等

代碼實現(xiàn)：

邊界問題：

? 解題的時候，一個非常重要的事情就是確定邊界問題。

? 在這題當(dāng)中，判斷條件為：若當(dāng)前字符（right）沒有出現(xiàn)過，則計算該子串的長度，否則將左指針（left）的位置重置為當(dāng)前字符（right）的位置。

? 這里有一個問題，假如輸入為 “txxmast”，當(dāng)右指針right移動到最后一位?t?時，此時的子串為"xmas"，按理說 t 并沒有出現(xiàn)在這個子串當(dāng)中，此時的字符串長度應(yīng)為5。但是由于之前的"t"在哈希表中的索引還是0，因此最后一個"t"會因為已經(jīng)出現(xiàn)在哈希表里，而被當(dāng)成重復(fù)字符不進(jìn)入計算，導(dǎo)致bug。

? 因此，針對此邊界問題，我們需要再加入一個判斷：若當(dāng)前字符已經(jīng)存在哈希表中，但它是上一個字符串里的字符（即它在哈希表中的索引小于當(dāng)前right），則當(dāng)前字符不屬于當(dāng)前子串，仍計算長度。

? 也就是上圖中紅色圈圈的部分。

? 參考：

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

https://blog.csdn.net/qq_19446965/article/details/104579511

https://medium.com/outco/how-to-solve-sliding-window-problems-28d67601a66