Go 面試題：滑動窗口技巧

很多同學學過滑動窗口算法，但是一做題就錯，這是因為有很多細節(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}

分析

1. 滿足left右滑動的條件：無重復字符，即右滑時window容器中每個元素值<=1

2. 是否更新結(jié)果值條件：在window中無重復的元素后，即for循環(huán)之后，判斷res-left與之前無重復字符串最大長度（res）之間關(guān)系

3. right右滑動變量變化：參照聲明的四個變量，這題只有winow和right變化

4. 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ū)間匹配

很明顯這又是一個求子串的問題，分析如下

1. 滿足left右滑動的條件：這題和前言中題類似，設(shè)一個target切片記錄目標區(qū)間每個元素的個數(shù)[A:1,B:1,C:1]，當window中所有目標元素個數(shù)（vaild）都達到target要求時，left右滑縮小區(qū)間

2. 是否更新結(jié)果值條件：在left右滑時，即for循環(huán)中判斷當前right-left與之前最小覆蓋子串之間關(guān)系

3. right右滑動變量變化：參照聲明的變量有當前區(qū)間window，達標元素個數(shù)vaild，窗口右邊界right

4. 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}

1. 題型：求子串、求子數(shù)組，在這樣的題目關(guān)鍵字中，我們可以考慮通過雙指針單向滑動剪枝出滿足條件的區(qū)間

2. 記住模板：一容（window），二變（left，right），三擴（right右移），四縮（left右移）

3. 思路：倆個條件（left右滑條件，是否更新結(jié)果值條件），倆個變化（right右滑動變量變化，left右滑動變量變化）

4. 易錯點：例如第二題每次滑動需要更新的變量很多，稍有不慎就會少更新某個變量，每次對照開始聲明的變量可以萬無一失