Go面試題型系列：滑動窗口技巧

本文是公衆號讀者上山打老虎的原創投稿，主要內容是講解算法技巧之滑動窗口。上山兄一直保持着刷題的習慣，並形成了自己的一套做題心得，當然他也是無情的 offer 收割機。同時上山兄會持續給本號投稿算法類文章，代碼示例均採用 Go 語言，希望該算法系列文章有助讀者更好地備戰面試。

在數組中查找一個數，可以使用二分法查找，但是算法問題中還有一些是在數組（或字符串）中查找一個子區間，這時滑動窗口就是一種很好的解決思路。

很多同學學過滑動窗口算法，但是一做題就錯，這是因爲有很多細節問題會在解答時出錯，本文將依次介紹該算法的模板，易錯點，分類題型，希望讀者看完之後能極大的提高做題速度以及準確度。

什麼是滑動窗口

概念

滑動窗口是雙指針算法的一種，利用雙指針在數組單一方向滑動，形成一個子區間，對子區間進行剪枝，最終得出滿足條件的解。

過程

window 中元素未完全包含 target 時，right 向右滑動

此時 window 包含 target 中所有元素，將 left 向右滑動

Go 代碼模板
func checkInclusion(nums []int, target []int) bool {
  window := make(map[byte]int, len(nums))
    left, right := 0, 0

    for right < len(nums) {
        c := nums[right]
        window[c]++
        //right右滑變量變化
        right++

        for 滿足left右滑條件 {
            //判斷區間是否滿足條件（可能在left右滑的前中後）

            d := nums[left]
            //left右滑變量的改動

            left++
        }
    }
    return false
}
易錯點

例題解析

值匹配

這道題是求最長子串，這裏我們需要敏銳地捕捉到 “子串” 關鍵詞。該題中，我們把字符串當做數組，“子串”就是子區間，這赤裸裸的就是滑動窗口的題型呀。

廢話不多說，直接先上模板！

func lengthOfLongestSubstring(s string) int {
    lens := len(s)
    window := make(map[byte]int, lens)
  left, right := 0, 0

    for right < lens{
        c := nums[right]
        window[c]++
        //right右滑變量變化
        right++

        for 滿足left右滑條件 {
            //判斷區間是否滿足條件（可能在left右滑的前中後）

            d := nums[left]
            //left右滑變量的改動

            left++
        }
    }
    return false
}

分析

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

  2. 是否更新結果值條件：在 window 中無重複的元素後，即 for 循環之後，判斷 res-left 與之前無重複字符串最大長度（res）之間關係

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

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

func lengthOfLongestSubstring(s string) int {
    lens := len(s)
    window := make(map[byte]int, lens)
    left, right, res := 0, 0, 0

  //right右滑動
    for right < lens {
        b := s[right]
        window[b]++
        right++
    //left右滑動
        for window[b] > 1 {
            c := s[left]
            window[c]--
            left++
        }
    //判斷區間是否滿足條件
        if right-left > res {
            res = right - left
        }
    }
    return res
}

區間匹配

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

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

  2. 是否更新結果值條件：在 left 右滑時，即 for 循環中判斷當前 right-left 與之前最小覆蓋子串之間關係

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

  4. left 右滑動變量變化：參照聲明的變量有起始位置 start，結果字符串長度 res，達標元素個數 vaild，當前區間 window，窗口左邊界 left

func minWindow(s string, t string) string {
  //變量初始化
    lens := len(s)
    lent := len(t)
    window := make(map[byte]int, lens)
    target := make(map[byte]int, lent)
    left, right, vaild := 0, 0, 0
    res := lens
    start := -1

    for i := 0; i < lent; i++ {
        target[t[i]]++
    }

  //right右滑動
    for right < lens {
        b := s[right]
        window[b]++
        if target[b] == window[b] {
            vaild++
        }
        right++

    //left右滑動
        for vaild == len(target) {
            c := s[left]
      //是否更新結果值
            if res >= right-left {
                start = left
                res = right - left
            }

            if window[c] == target[c] {
                vaild--
            }
      window[c]--
            left++
        }
    }
    if start == -1 {
        return ""
    }
    return s[start : start+res]
}

總結

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

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

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

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

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/_8GxqQGdIsdyQHkijiiFqA

猜你喜歡