滑动窗口思想

模板

1
/* 滑动窗口算法框架 */
2
void slidingWindow(string s, string t) {
3
unordered_map<char, int> need, window;
4
for (char c : t) need[c]++;
5
6
int left = 0, right = 0;
7
int valid = 0;
8
while (right < s.size()) {
9
// c 是将移入窗口的字符
10
char c = s[right];
11
// 右移窗口
12
right++;
13
// 进行窗口内数据的一系列更新
14
...
15
16
/*** debug 输出的位置 ***/
17
printf("window: [%d, %d)\n", left, right);
18
/********************/
19
20
// 判断左侧窗口是否要收缩
21
while (window needs shrink) {
22
// d 是将移出窗口的字符
23
char d = s[left];
24
// 左移窗口
25
left++;
26
// 进行窗口内数据的一系列更新
27
...
28
}
29
}
30
}
Copied!
需要变化的地方
  • 1、右指针右移之后窗口数据更新
  • 2、判断窗口是否要收缩
  • 3、左指针右移之后窗口数据更新
  • 4、根据题意计算结果

示例

给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字母的最小子串
1
func minWindow(s string, t string) string {
2
// 保存滑动窗口字符集
3
win := make(map[byte]int)
4
// 保存需要的字符集
5
need := make(map[byte]int)
6
for i := 0; i < len(t); i++ {
7
need[t[i]]++
8
}
9
// 窗口
10
left := 0
11
right := 0
12
// match匹配次数
13
match := 0
14
start := 0
15
end := 0
16
min := math.MaxInt64
17
var c byte
18
for right < len(s) {
19
c = s[right]
20
right++
21
// 在需要的字符集里面,添加到窗口字符集里面
22
if need[c] != 0 {
23
win[c]++
24
// 如果当前字符的数量匹配需要的字符的数量,则match值+1
25
if win[c] == need[c] {
26
match++
27
}
28
}
29
30
// 当所有字符数量都匹配之后,开始缩紧窗口
31
for match == len(need) {
32
// 获取结果
33
if right-left < min {
34
min = right - left
35
start = left
36
end = right
37
}
38
c = s[left]
39
left++
40
// 左指针指向不在需要字符集则直接跳过
41
if need[c] != 0 {
42
// 左指针指向字符数量和需要的字符相等时,右移之后match值就不匹配则减一
43
// 因为win里面的字符数可能比较多,如有10个A,但需要的字符数量可能为3
44
// 所以在压死骆驼的最后一根稻草时,match才减一,这时候才跳出循环
45
if win[c] == need[c] {
46
match--
47
}
48
win[c]--
49
}
50
}
51
}
52
if min == math.MaxInt64 {
53
return ""
54
}
55
return s[start:end]
56
}
Copied!
给定两个字符串 s1s2,写一个函数来判断 s2 是否包含 s1 的排列。
1
func checkInclusion(s1 string, s2 string) bool {
2
win := make(map[byte]int)
3
need := make(map[byte]int)
4
for i := 0; i < len(s1); i++ {
5
need[s1[i]]++
6
}
7
left := 0
8
right := 0
9
match := 0
10
for right < len(s2) {
11
c := s2[right]
12
right++
13
if need[c] != 0 {
14
win[c]++
15
if win[c] == need[c] {
16
match++
17
}
18
}
19
// 当窗口长度大于字符串长度,缩紧窗口
20
for right-left >= len(s1) {
21
// 当窗口长度和字符串匹配,并且里面每个字符数量也匹配时,满足条件
22
if match == len(need) {
23
return true
24
}
25
d := s2[left]
26
left++
27
if need[d] != 0 {
28
if win[d] == need[d] {
29
match--
30
}
31
win[d]--
32
}
33
}
34
}
35
return false
36
}
Copied!
给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。
1
func findAnagrams(s string, p string) []int {
2
win := make(map[byte]int)
3
need := make(map[byte]int)
4
for i := 0; i < len(p); i++ {
5
need[p[i]]++
6
}
7
left := 0
8
right := 0
9
match := 0
10
ans:=make([]int,0)
11
for right < len(s) {
12
c := s[right]
13
right++
14
if need[c] != 0 {
15
win[c]++
16
if win[c] == need[c] {
17
match++
18
}
19
}
20
// 当窗口长度大于字符串长度,缩紧窗口
21
for right-left >= len(p) {
22
// 当窗口长度和字符串匹配,并且里面每个字符数量也匹配时,满足条件
23
if right-left == len(p)&& match == len(need) {
24
ans=append(ans,left)
25
}
26
d := s[left]
27
left++
28
if need[d] != 0 {
29
if win[d] == need[d] {
30
match--
31
}
32
win[d]--
33
}
34
}
35
}
36
return ans
37
}
Copied!
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
1
func lengthOfLongestSubstring(s string) int {
2
// 滑动窗口核心点:1、右指针右移 2、根据题意收缩窗口 3、左指针右移更新窗口 4、根据题意计算结果
3
if len(s)==0{
4
return 0
5
}
6
win:=make(map[byte]int)
7
left:=0
8
right:=0
9
ans:=1
10
for right<len(s){
11
c:=s[right]
12
right++
13
win[c]++
14
// 缩小窗口
15
for win[c]>1{
16
d:=s[left]
17
left++
18
win[d]--
19
}
20
// 计算结果
21
ans=max(right-left,ans)
22
}
23
return ans
24
}
25
func max(a,b int)int{
26
if a>b{
27
return a
28
}
29
return b
30
}
Copied!

总结

  • 和双指针题目类似,更像双指针的升级版,滑动窗口核心点是维护一个窗口集,根据窗口集来进行处理
  • 核心步骤
    • right 右移
    • 收缩
    • left 右移
    • 求结果

练习

最近更新 1yr ago
复制链接