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

叁歲伎倆 2022-09-03 06:14 202阅读 0赞

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

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

![9cffcc5bc1833e4a7f0b606dfaacaf7d.png][]

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

**什么是滑动窗口**

###### 概念 ######

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

###### 过程 ######

window中元素未完全包含target时，right向右滑动

![6de2b650251b6c67601d5b5c03fd2dd8.png][]

![a3c82dc7deb46ad50cc0b8e5bd688279.png][]

此时window包含target中所有元素，将left向右滑动

![e25e358b7354d64675002fabb717a485.png][]

###### 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右滑动时，先判断是否满足条件，再做变量值的变化，颠倒会导致第一次满足条件的解漏掉

**例题解析**

#### 值匹配 ####

![dd43b86fc4f8f4db11468a62c3db0d52.png][]

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

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

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}

#### 区间匹配 ####

![3e7d8633d2300d39c3b1d7cc10a789d4.png][]

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

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

**往期推荐**

*  [同步原语的基石][Link 1]  
    
 *  [一文读懂channel设计][channel]  
    
 *  [详解逃逸分析][Link 2]  
    
 *  [CPU缓存体系对Go程序的影响][CPU_Go]  
    
 *  [含有CGO代码的项目如何实现跨平台编译][CGO]
 *  [Go精妙的互斥锁设计][Go]

![159c1fc4cf578ec6339b3e10696cdc6d.png][]

**机器铃砍菜刀**

欢迎添加小菜刀微信

加入Golang分享群学习交流！

感谢你的**点赞**和**在看**哦~

![785d78c68573bc1622f929f3f4729af1.gif][]

[9cffcc5bc1833e4a7f0b606dfaacaf7d.png]: /images/20220829/c7ceedc0858245489e37251998125d30.png
[6de2b650251b6c67601d5b5c03fd2dd8.png]: /images/20220829/af402e24573e403988c3e128bc43fbe1.png
[a3c82dc7deb46ad50cc0b8e5bd688279.png]: /images/20220829/38b361e20d27456f8dea2034a58661b1.png
[e25e358b7354d64675002fabb717a485.png]: /images/20220829/577e44b603ac467d9428fd8d10605315.png
[dd43b86fc4f8f4db11468a62c3db0d52.png]: /images/20220829/d7c5c26bd94f43febae4bf6d16865288.png
[3e7d8633d2300d39c3b1d7cc10a789d4.png]: /images/20220829/6298a4d3f6be4f309e5544e819978713.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzIwNTA4MDAwMQ%3D%3D&chksm=97371030a04099263dfbf16dc24438f409166a053fd9fef802f9f9e4f8fd3c4aba9dd97df8f8&idx=1&mid=2247484574&scene=21&sn=5bbe2668e64455f428c70f00c09f28a2#wechat_redirect
[channel]: http://mp.weixin.qq.com/s?__biz=MzIwNTA4MDAwMQ%3D%3D&chksm=97371768a0409e7e1d24517dc26cab0b6a3498595c2462d9ddec2bdad47bcded069e256e0633&idx=1&mid=2247484358&scene=21&sn=1fc82fb351d9863a45f3868d85b0d19a#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzIwNTA4MDAwMQ%3D%3D&chksm=973710d5a04099c3c2dde737eb9de31eddb9d3707ea5885abed6a06fa7fc9855fad7de8561f7&idx=1&mid=2247484539&scene=21&sn=be23b39e21067e3017f15afb36271570#wechat_redirect
[CPU_Go]: http://mp.weixin.qq.com/s?__biz=MzIwNTA4MDAwMQ%3D%3D&chksm=973710e8a04099fe6f113c38a9e9940c0ff590877ad7ba0a0f4c383356e91619574f052a6064&idx=1&mid=2247484486&scene=21&sn=83ebd97be71caad3537502e459182f88#wechat_redirect
[CGO]: http://mp.weixin.qq.com/s?__biz=MzIwNTA4MDAwMQ%3D%3D&chksm=973710b1a04099a79359efe74b4eb2595ac98fefa8ce347affe012f55b913178537764d583fa&idx=1&mid=2247484447&scene=21&sn=7697120800d8be5833c163d99e09c858#wechat_redirect
[Go]: http://mp.weixin.qq.com/s?__biz=MzIwNTA4MDAwMQ%3D%3D&chksm=9737106ba040997d4bdd3aa077186d89568b0019b4b83164dc59b9b2e8c4a408e4496aa93d1a&idx=1&mid=2247484613&scene=21&sn=d79c33be877e8124d050ed3669b26e24#wechat_redirect
[159c1fc4cf578ec6339b3e10696cdc6d.png]: /images/20220829/833c0632e030410a8dce0d7f0716e762.png
[785d78c68573bc1622f929f3f4729af1.gif]: /images/20220829/03c1378f714a46e1856fd7952819dd0f.png