Go 面试题:滑动窗口技巧

Go语言精选

共 7768字,需浏览 16分钟

 ·

2021-04-06 19:41

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

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

什么是滑动窗口

概念

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

过程

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


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


Go代码模板
 1func checkInclusion(nums []int, target []int) bool {
2  window := make(map[byte]intlen(nums))
3    left, right := 00
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 := 00
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 := 000
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 := 000
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. 易错点:例如第二题每次滑动需要更新的变量很多,稍有不慎就会少更新某个变量,每次对照开始声明的变量可以万无一失



推荐阅读


福利

我为大家整理了一份从入门到进阶的Go学习资料礼包,包含学习建议:入门看什么,进阶看什么。关注公众号 「polarisxu」,回复 ebook 获取;还可以回复「进群」,和数万 Gopher 交流学习。

浏览 39
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报