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]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}
分析
满足left右滑动的条件:无重复字符,即右滑时window容器中每个元素值<=1
是否更新结果值条件:在window中无重复的元素后,即for循环之后,判断res-left与之前无重复字符串最大长度(res)之间关系
right右滑动变量变化:参照声明的四个变量,这题只有winow和right变化
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}
区间匹配
很明显这又是一个求子串的问题,分析如下
满足left右滑动的条件:这题和前言中题类似,设一个target切片记录目标区间每个元素的个数[A:1,B:1,C:1],当window中所有目标元素个数(vaild)都达到target要求时,left右滑缩小区间
是否更新结果值条件:在left右滑时,即for循环中判断当前right-left与之前最小覆盖子串之间关系
right右滑动变量变化:参照声明的变量有当前区间window,达标元素个数vaild,窗口右边界right
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}
总结
题型:求子串、求子数组,在这样的题目关键字中,我们可以考虑通过双指针单向滑动剪枝出满足条件的区间
记住模板:一容(window),二变(left,right),三扩(right右移),四缩(left右移)
思路:俩个条件(left右滑条件,是否更新结果值条件),俩个变化(right右滑动变量变化,left右滑动变量变化)
易错点:例如第二题每次滑动需要更新的变量很多,稍有不慎就会少更新某个变量,每次对照开始声明的变量可以万无一失
推荐阅读