0%

滑动窗口解题技巧

算法思想

  • 在字符串 S 中使用双指针的左右指针技巧,初始化 left = right = 0,索引闭区间 [left, right] 称为一个窗口
  • 先不断增加 right 指针扩大窗口 [left, right],直到窗口中的字符串符合要求(包含了 T 中的所有字符串)
  • 此时,停止增加 right,转而不断增加 left 指针来缩小窗口 [left, right],直到窗口中的字符串不再符合要求 (不包含 T 中的所有字符了)。同时,每次增加 left,都要更新一轮结果。
  • 重复 2 - 3 ,直到 right 到达尽头。

框架代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
string s, t;
int left = 0,right = 0;

string res = s;
while (right < s.size()) {
window.add(s[right])
right ++;
// 如果符合要求,移动left缩小窗口
while (window 符合要求) {
// 如果这个窗口的子串更短,则更新res
res = minLen(res, window);
window.remove(s[left]);
left++;
}
}
return res;

那么我们要如何判断window即子串 s[left...right] 是否符合要求,是否包含 t 的所有字符呢?

可以用两个hash表来做计数器,一个记录t的字符以及出现次数,另一个window则记录当前窗口所包含的字符及出现的次数,如果window包含所有needs中的键,且这些键对应的值都大于等于needs中的值,那么就可以知道当前窗口符合要求了,可以开始移动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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
stirng s, t;
// 在s中找t的最小覆盖子串
int left = 0,right = 0;
string res = s;

// 相当于两个计数器
unordered_map<char, int> window;
unordered_map<char, int> needs;

for (char c : t) {
needs[c] ++;
}

// 记录 window 中已经有多少字符符合要求了
int match = 0;

while (right < s.size()) {
char c1 = s[right];
if (needs.count(c1)) {
// 加入window
window[c1] ++;
if (window[c1] === needs[c1]) {
// 字符c1点出现符合次数了
match ++;
}
}
right ++;

// window 中的字符已符合 needs 的要求了
while (match === needs.size()) {
// 更新结果res
res = minLen(res, window);
char c2 = s[left];
if (needs.count(c2)) {
// 移出 window
window[c2] --;
if (window[c2] < needs[c2]) {
// 字符 c2 出现次数不再符合要求
match --;
}
}
}
}
return res;

lc76 最小覆盖子串

这题可以套一套我们上面的板子:

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
// s中能覆盖t的最小子串
// s = "ADOBECODEBANC",t = "ABC"
// res = "BNAC"
var minWindow = function (s, t) {
s = s.split('')
t = t.split('')
let tMap = new Map()
let window = new Map()
let min = Number.MAX_SAFE_INTEGER
let start = 0
let l = 0,
r = 0
for (let i = 0; i < t.length; i++) {
tMap.set(t[i], tMap.has(t[i]) ? tMap.get(t[i]) + 1 : 1)
}
let match = 0
while (r < s.length) {
let c1 = s[r]
if (tMap.has(c1)) {
window.set(c1, window.has(c1) ? window.get(c1) + 1 : 1)
if (window.get(c1) === tMap.get(c1)) {
match++
}
}
r++
// 如果window中的串已经符合要求了,开始移动左边,找符合条件的最小值
while (match === tMap.size) {
if (r - l < min) {
start = l
min = r - l
}
// 更新一下最短的字符串
let c2 = s[l]
if (tMap.has(c2)) {
window.set(c2, window.get(c2) - 1)
if (window.get(c2) < tMap.get(c2)) {
match--
}
}
l++
}
}
return min === Number.MAX_SAFE_INTEGER ? '' : s.join('').slice(start, start + min)
}

// console.log(minWindow('ADOBECODEBANC', 'ABC'))