滑窗专题
# 滑窗专题(sliding window)
# 题目
题号 | 题目 | 难度 |
---|---|---|
76 | 最小覆盖子串 (opens new window) | Hard |
567 | 字符串的排列 (opens new window) | Medium |
438 | 找到字符串中所有字母异位词 (opens new window) | Medium |
3 | 无重复字符的最长子串 (opens new window) | Medium |
# 思路
# 2.1 题目特征
这种题目的特征:
首先是在字符串(或数组)上,找某一段最长或最短满足要求的字符串(或数组),返回字符串(或数组)或其长度。
其中要求如果是无序的要求,则更容易让人想到滑窗,如果是有序反而容易让人想到字符串匹配(如KMP等)
# 2.2 代码框架
框架参考labuladong的思路:
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/
printf("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
整体的思路是,right右移的大循环套着left左移的循环。如果不满足条件,右侧的right就会一直扩张,否则left就会往右缩。
# 参考
【1】https://mp.weixin.qq.com/s/ioKXTMZufDECBUwRRp3zaA
编辑 (opens new window)
上次更新: 2021/06/03, 14:04:20