参阅基础
简介
遇到与给定对象的连续子区间有关的问题时，一个很容易联想到的技巧就是滑动窗口。
滑窗的思路非常简单，就是维护一个窗口，不断滑动，然后更新答案。
但滑窗的难点不是算法的思路，而是各种细节问题。比如如何向窗口中添加新元素，如何缩小窗口，在窗口滑动的哪个阶段更新结果。
以下这套滑动窗口算法的代码框架，标记了实现中需要注意的细节，和输出 debug 的位置。以后遇到相关的问题，只需要默写出该框架，然后改三个地方就行：
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
| const slidingWindow = (s) => {
const win = [];
let left = 0,
right = 0;
while (right < s.length) {
const c = s[right];
right++;
console.log("window", win);
while(win needs shrink){
const d = s[left];
left++;
}
}
};
|
其中两处 ... 表示的更新窗口数据的地方，直接往里面填逻辑就行。而且这两处 ... 的操作分别是扩大和缩小窗口的更新操作，它们的操作是完全对称的。
另外，虽然滑动窗口代码框架中有一个嵌套的 while 循环，但算法的时间复杂度依然是 O(N)
，其中 N 是输入字符串/数组的长度。因为字符串（或数组）中的每个元素都只会进入窗口一次，然后被移出窗口一次，不会有某些元素多次进入和离开窗口的情况。所以算法的时间复杂度就和字符串（或数组）的长度成正比。
相关习题
LeetCode 76. 最小覆盖子串
题目
来源：https://leetcode.cn/problems/minimum-window-substring/
难度：困难
我的题解
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
var minWindow = function(s, t) {
let needMap = new Map()
let win = new Map()
let vaild = 0
let start = 0,len = 0;
let isFirst = true
for(index in t){
if(needMap.has(t[index])){
needMap.set(t[index],needMap.get(t[index]) + 1)
}else{
win.set(t[index],0)
needMap.set(t[index],1)
}
}
let needLen = needMap.size
let left = 0,right = 0;
while(right < s.length){
const c = s[right];
right++;
if(needMap.get(c)){
win.set(c,win.get(c) + 1)
if(win.get(c) == needMap.get(c)){
vaild ++;
}
}
console.log(needLen,vaild)
while(needLen === vaild){
const d = s[left];
if(isFirst){
start = left
len = right
isFirst = false
}else{
if(right - left < len){
start = left
len = right - left
}
}
left++;
if(needMap.get(d)){
win.set(d,win.get(d) - 1)
if(win.get(d) < needMap.get(d)){
vaild --;
}
}
}
}
return s.substring(start,start + len)
};
|
