前言
這不是一個給一道題目然後告訴你題解的系列，而是對於一系列題目進行分類，找出他們解題規律並得出大致框架程式碼的文章。吃透解一系列題目的規律比會解單個題目有用得多，畢竟你總會遇到沒刷過的題。
正文大家對於滑動視窗應該不陌生，在 TCP 協議中就有這個概念的出現，用於控制網路流量，避免擁塞發生。
在演算法中這個思想也是類似的，多用於解決在一段連續的區間中尋找滿足條件的問題，比如說給定一個字串，尋找出無重複字元的最長子串。該思路主要應用於陣列及字串的資料結構中。
示例滑動視窗主要思路是維護一對指標，在一定條件內右移右指標擴大視窗大小直到視窗內的解不滿足題意，此時我們需要根據情況移動左指標，重複移動左右指標的操作並在區間內求解，直到雙指標不能再移動。
以 尋找出無重複字元的最長子串 題目為例，根據上述的思路解題就會很方便：
var lengthOfLongestSubstring = function(s) { // 用於儲存指標移動過程中的值 let map = {} // 雙指標 let left = 0 let right = 0 // 結果 let count = 0 // 指標移動終止條件 while (right < s.length) { const char = s[right] // 根據題意我們需要尋找不重複的最長子串 // 當 char 出現時我們需要移動左指標到重複字元的下一位 if (char in map) { left = Math.max(left, map[char] + 1) } // 求解 count = Math.max(count, right - left + 1) // 移動右指標並存下索引 map[char] = right++ } return count};此題為高頻題，大家務必掌握
框架根據上題我們可以得出一個滑動視窗解題的大致框架的虛擬碼，
let left = 0let right = 0while (right < size) { 獲取當前索引資料 right++ 資料更新等操作 while (視窗需要縮小) { left++ 資料移除等操作 }}框架中需要變化的幾點如下：
右指標右移後資料的更新判斷視窗何時需要縮小左指標右移後資料的更新根據題目求最優解接下來我們根據這個框架程式碼來試著解決幾道題目。
實戰209. 長度最小的子陣列解題思路：
移動右指標並將移動後的值累加儲存起來當累加值大於 s 時移動左指標縮小視窗，此時需要更新累加值及我們需要的解var minSubArrayLen = function(s, nums) { // 定義雙指標 let left = 0 let right = 0 // 求解需要用到的變數 let length = Infinity let sum = 0 // 指標移動終止條件 while (right < nums.length) { // 獲取當前索引資料 sum += nums[right] // 縮小視窗條件 while (sum >= s) { // 求解 length = Math.min(length, right - left + 1) // 縮小視窗 sum -= nums[left++] } // 擴大視窗 right++ } return length === Infinity ? 0 : length};這道題目是 Leetcode 的第 209 題，答案可以說除了小部分的微調之外，基本套用了框架程式碼。後續的題目大家可以繼續跟著這個思路解題，快速掌握透過滑動視窗來解題的套路。
438. 找到字串中所有字母異位詞解題思路：
透過雜湊表儲存 p 中的字元出現次數移動右指標判斷當前字元是否還符合條件不符合條件時移動左指標縮小視窗，此時需要更新雜湊表當前字元不存在雜湊表時說明雙指標可以直接跳到下一位var findAnagrams = function(s, p) { if (!s.length || !p.length || s.length < p.length) return [] // 求解需要用到的變數 const map = {} const result = [] // 定義雙指標 let left = 0, right = 0 // 把字串 p 中的字元透過 hash 儲存起來 for (let i = 0; i < p.length; i++) { const char = p[i] if (!(char in map)) { map[char] = 0 } map[char] += 1 } // 指標移動終止條件 while (right < s.length) { const char = s[right] // map 中存在字元就移動右指標 if (map[char] > 0) { map[char] -= 1 right++ // 否則判斷左指標所指向的字元是否存在 map 中 } else if (map[s[left]] >= 0) { map[s[left]] += 1 left++ // 不存在的話把左右指標全部挪到下一位 } else { left = right += 1 } // 儲存正確解 if (right - left === p.length) { result.push(left) } } return result};這道題目和之前的 「找到字串中所有字母異位詞」思路很類似：
透過雜湊表儲存 t 中的字元出現次數移動右指標判斷當前字元是否還符合條件不符合條件時移動左指標縮小視窗，此時需要更新雜湊表var minWindow = function(s, t) { // 定義雙指標 let left = 0, right = 0 // 求解需要用到的變數 let length = Infinity let map = {} // 遇到 t 中存在的字元時更新 match，注意 t 中存在的字元可能在 s 中出現多次 // 因此並不是每次都需要更新 match let match = 0 // 記錄最短子串開始位置，不能用 left let start = 0 // 把字串 t 中的字元透過 hash 儲存起來 for (let i = 0; i < t.length; i++) { const char = t[i] if (!(char in map)) { map[char] = 0 } map[char] += 1 } // 指標移動終止條件 while (right < s.length) { const char = s[right] // 右指標移動時更新資料 if (char in map) { map[char] -= 1 if (map[char] >= 0) match += 1 } // 縮小視窗條件 while (match === t.length) { // 尋找到更佳解，儲存資料 if (length > right - left + 1) { length = right - left + 1 start = left } // 移動左指標並且更新資料 const char = s[left++] if (char in map) { if (map[char] === 0) match -= 1 map[char] += 1 } } // 移動右指標 right++ } return length === Infinity ? '' : s.substring(start, start + length)};經過上面幾道題目的練習，大家應該能看出滑動視窗的思路多用於解決陣列及字串中子元素的問題。
最新評論