时间：   |   分类：     |   阅读： 1891 字 ~4分钟

面试题型系列：滑动窗口技巧

本文是公众号读者上山打老虎的第二篇原创投稿，主要内容是讲解算法技巧之滑动窗口。上山兄一直保持着刷题的习惯，并形成了自己的一套做题心得，当然他也是无情的offer收割机。同时上山兄会持续给本号投稿算法类文章，代码示例均采用Go语言，希望该算法系列文章有助读者更好地备战面试。

在数组中查找一个数，可以使用二分法查找，但是算法问题中还有一些是在数组（或字符串）中查找一个子区间，这时滑动窗口就是一种很好的解决思路。

很多同学学过滑动窗口算法，但是一做题就错，这是因为有很多细节问题会在解答时出错，本文将依次介绍该算法的模板，易错点，分类题型，希望读者看完之后能极大的提高做题速度以及准确度。

什么是滑动窗口

概念

滑动窗口是双指针算法的一种，利用双指针在数组单一方向滑动，形成一个子区间，对子区间进行剪枝，最终得出满足条件的解。

过程

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            //判断区间是否满足条件（可能在left右滑的前中后）
13
14            d := nums[left]
15            //left右滑变量的改动
16
17            left++
18        }
19    }
20    return false
21}
易错点
  • left和right滑动时，容易漏掉某个变量的值变化，这里教大家一个技巧，每次写完复查前面声明的变量，在滑动时是否改变
  • left右滑动时，先判断是否满足条件，再做变量值的变化，颠倒会导致第一次满足条件的解漏掉

例题解析

值匹配

这道题是求最长子串，这里我们需要敏锐地捕捉到“子串”关键词。该题中，我们把字符串当做数组，“子串”就是子区间，这赤裸裸的就是滑动窗口的题型呀。

废话不多说，直接先上模板！

 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            //判断区间是否满足条件（可能在left右滑的前中后）
14
15            d := nums[left]
16            //left右滑变量的改动
17
18            left++
19        }
20    }
21    return false
22}

分析

  1. 满足left右滑动的条件：无重复字符，即右滑时window容器中每个元素值<=1
  2. 是否更新结果值条件：在window中无重复的元素后，即for循环之后，判断res-left与之前无重复字符串最大长度（res）之间关系
  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    //判断区间是否满足条件
18        if right-left > res {
19            res = right - left
20        }
21    }
22    return res
23}

区间匹配

很明显这又是一个求子串的问题，分析如下

  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
 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      //是否更新结果值
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. 题型：求子串、求子数组，在这样的题目关键字中，我们可以考虑通过双指针单向滑动剪枝出满足条件的区间

  2. 记住模板：一容（window），二变（left，right），三扩（right右移），四缩（left右移）

  3. 思路：俩个条件（left右滑条件，是否更新结果值条件），俩个变化（right右滑动变量变化，left右滑动变量变化）

  4. 易错点：例如第二题每次滑动需要更新的变量很多，稍有不慎就会少更新某个量，每次对照开始声明的变量可以万无一失

转转自机器铃砍柴刀

0%