Go 面試題：滑動窗口技巧
在數(shù)組中查找一個數(shù)，可以使用二分法查找，但是算法問題中還有一些是在數(shù)組（或字符串）中查找一個子區(qū)間，這時滑動窗口就是一種很好的解決思路。
很多同學學過滑動窗口算法，但是一做題就錯，這是因為有很多細節(jié)問題會在解答時出錯，本文將依次介紹該算法的模板，易錯點，分類題型，希望讀者看完之后能極大的提高做題速度以及準確度。
什么是滑動窗口
概念
滑動窗口是雙指針算法的一種，利用雙指針在數(shù)組單一方向滑動，形成一個子區(qū)間，對子區(qū)間進行剪枝，最終得出滿足條件的解。
過程
window中元素未完全包含target時，right向右滑動
此時window包含target中所有元素，將left向右滑動
Go代碼模板
1func checkInclusion(nums []int, target []int) bool {
2 window := make(map[byte]int, len(nums))
3 left, right := 0, 0
4
5 for right < len(nums) {
6 c := nums[right]
7 window[c]++
8 //right右滑變量變化
9 right++
10
11 for 滿足left右滑條件 {
12 //判斷區(qū)間是否滿足條件（可能在left右滑的前中后）
13
14 d := nums[left]
15 //left右滑變量的改動
16
17 left++
18 }
19 }
20 return false
21}
易錯點
left和right滑動時，容易漏掉某個變量的值變化，這里教大家一個技巧，每次寫完復查前面聲明的變量，在滑動時是否改變
left右滑動時，先判斷是否滿足條件，再做變量值的變化，顛倒會導致第一次滿足條件的解漏掉
例題解析
值匹配
這道題是求最長子串，這里我們需要敏銳地捕捉到“子串”關(guān)鍵詞。該題中，我們把字符串當做數(shù)組，“子串”就是子區(qū)間，這赤裸裸的就是滑動窗口的題型呀。
廢話不多說，直接先上模板！
1func lengthOfLongestSubstring(s string) int {
2 lens := len(s)
3 window := make(map[byte]int, lens)
4 left, right := 0, 0
5
6 for right < lens{
7 c := nums[right]
8 window[c]++
9 //right右滑變量變化
10 right++
11
12 for 滿足left右滑條件 {
13 //判斷區(qū)間是否滿足條件（可能在left右滑的前中后）
14
15 d := nums[left]
16 //left右滑變量的改動
17
18 left++
19 }
20 }
21 return false
22}
分析
滿足left右滑動的條件：無重復字符，即右滑時window容器中每個元素值<=1
是否更新結(jié)果值條件：在window中無重復的元素后，即for循環(huán)之后，判斷res-left與之前無重復字符串最大長度（res）之間關(guān)系
right右滑動變量變化：參照聲明的四個變量，這題只有winow和right變化
left右滑動變量變化：參照聲明的四個變量，這題只有winow和left變化
1func lengthOfLongestSubstring(s string) int {
2 lens := len(s)
3 window := make(map[byte]int, lens)
4 left, right, res := 0, 0, 0
5
6 //right右滑動
7 for right < lens {
8 b := s[right]
9 window[b]++
10 right++
11 //left右滑動
12 for window[b] > 1 {
13 c := s[left]
14 window[c]--
15 left++
16 }
17 //判斷區(qū)間是否滿足條件
18 if right-left > res {
19 res = right - left
20 }
21 }
22 return res
23}
區(qū)間匹配
很明顯這又是一個求子串的問題，分析如下
滿足left右滑動的條件：這題和前言中題類似，設(shè)一個target切片記錄目標區(qū)間每個元素的個數(shù)[A:1,B:1,C:1]，當window中所有目標元素個數(shù)（vaild）都達到target要求時，left右滑縮小區(qū)間
是否更新結(jié)果值條件：在left右滑時，即for循環(huán)中判斷當前right-left與之前最小覆蓋子串之間關(guān)系
right右滑動變量變化：參照聲明的變量有當前區(qū)間window，達標元素個數(shù)vaild，窗口右邊界right
left右滑動變量變化：參照聲明的變量有起始位置start，結(jié)果字符串長度res，達標元素個數(shù)vaild，當前區(qū)間window，窗口左邊界left
1func minWindow(s string, t string) string {
2 //變量初始化
3 lens := len(s)
4 lent := len(t)
5 window := make(map[byte]int, lens)
6 target := make(map[byte]int, lent)
7 left, right, vaild := 0, 0, 0
8 res := lens
9 start := -1
10
11 for i := 0; i < lent; i++ {
12 target[t[i]]++
13 }
14
15 //right右滑動
16 for right < lens {
17 b := s[right]
18 window[b]++
19 if target[b] == window[b] {
20 vaild++
21 }
22 right++
23
24 //left右滑動
25 for vaild == len(target) {
26 c := s[left]
27 //是否更新結(jié)果值
28 if res >= right-left {
29 start = left
30 res = right - left
31 }
32
33 if window[c] == target[c] {
34 vaild--
35 }
36 window[c]--
37 left++
38 }
39 }
40 if start == -1 {
41 return ""
42 }
43 return s[start : start+res]
44}總結(jié)
題型：求子串、求子數(shù)組，在這樣的題目關(guān)鍵字中，我們可以考慮通過雙指針單向滑動剪枝出滿足條件的區(qū)間
記住模板：一容（window），二變（left，right），三擴（right右移），四縮（left右移）
思路：倆個條件（left右滑條件，是否更新結(jié)果值條件），倆個變化（right右滑動變量變化，left右滑動變量變化）
易錯點：例如第二題每次滑動需要更新的變量很多，稍有不慎就會少更新某個變量，每次對照開始聲明的變量可以萬無一失
推薦閱讀