滑动窗口
一.滑动窗口基本思想
滑动窗口主要用来解决子串问题，先说下算法的基本逻辑：
使用左右指针维护一个窗口，先移动右指针直到窗口中的字符串符合要求，然后移动左指针缩短字串，直到窗口不符合要求，然后再移动右指针，再左指针，直到右指针到达数组边界。在这个过程中通过一个start和一个len来记录最小字串
基本算法思路：
1
2
3
4
5
6
7
8
9
10
11
12
| int left=0,right=0;
while(right<s.size()){
window.add(s[right]);
right++;
while(window need shrink){
window.remove(s[left]);
left++;
}
}
|
有了基本思路后我们开始编写具体代码框架，先介绍下用到的几个变量：
使用哈希表need和window分别记录需要凑齐的字符和窗口中的字符，使用一个变量valid来记录窗口中符合要求字符的个数（当valid==need.size()时表示窗口符合要求），使用start和len记录最小的字串，使用left和right代表窗口（注意是左闭右开的）
二.滑动窗口基本框架
所以这类算法的框架为
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| void slidingWindow(string s,string t){
unordered_map<char,int> need,window;
for(char c:t)need[c]++;
int left=right=0;
int valid=0;
while(right<s.size()){
char c=s[right];
right++;
while(valid==need.size()){
char d=s[left];
left++;
}
}
}
|
我们找个具体例子试一下
76最小覆盖字串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
虽然整体框架就是先移动右指针当符合条件再移动左指针直到不满足条件，但是有很多细节非常容易犯错，我将会再下面总结总结。
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
| string minWindow(string s, string t) {
if(s.size()<t.size())
return "";
unordered_map<char,int> need,window;
for(char c:t)need[c]++;
int start=0,len=INT_MAX;
int left=0,right=0,valid=0;
while (right<s.size()){
char c=s[right];
right++;
if(need.count(c)){
window[c]++;
if(window[c]==need[c]){
valid++;
}
}
while (valid==need.size()){
if(right-left<len){
start=left;
len=right-left;
}
char c=s[left];
left++;
if(need.count(c)){
if(window[c]==need[c]){
valid--;
}
window[c]--;
}
}
}
return len==INT_MAX?"":s.substr(start,len);
}
|
总结：
1.我们在移动右指针更新window和valid时，要注意只有当need.count(c)条件满足时才更新window，因为如果need中没有这个字符，更新了window没有意义，然后再更新window后要检测window[c]==need[c]，满足才能更新valid，换句话说，更新valid的条件是window[c]==need[c]
2.进入left右移循环后更新window和valid时，要先检测window[c]==need[c]，如果满足再valid–,不满足则不变动valid，因为window[c]可能会大于need[c]，因此不是每次window[c]减少时valid都要减少。
3.关于start和len的更新，我放到了left右移循环的开头，因为每次进入这个循环都表示此时窗口中符合了条件，注意更新这个两个值的条件为right-left<len
三.几种题型
1.双字符串不定大小滑动窗口
以上面的leetcode76为例，求A中B的字串，这样的滑动窗口大小是不固定的，移动方法就是先右指针右移，窗口符合要求后再左指针右移，直到窗口不符合要求再移右指针，如此重复直到右指针到达边界
2.双字符串固定大小滑动窗口
以leetcode438为例
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
这种滑动窗口就是在上面的基础上固定了窗口的大小，体现在代码上就是初始化right时right=p.size()-1，并且移动窗口时左右指针同时移动，每一次移动完毕以后检测valid==need.size()
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
| #include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
if(s.size()<p.size())
return {};
vector<int> result;
unordered_map<char,int>need ,window;
for (char c:p) need[c]++;
int left=0,right=p.size()-1,valid=0;
for (int i = 0; i <=right ; ++i) {
char c=s[i];
if(need.count(c)){
window[c]++;
if(window[c]==need[c])
valid++;
}
}
if(valid==need.size())
result.emplace_back(left);
while (right<s.size()){
char c=s[left];
if(need.count(c)){
if(window[c]==need[c])
valid--;
window[c]--;
}
right++;left++;
c=s[right];
if(need.count(c)){
window[c]++;
if(window[c]==need[c])
valid++;
}
if(valid==need.size())
result.emplace_back(left);
}
return result;
}
};
|
3.单字符串不定大小滑动窗口
以leetcode003为例
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度
解答这道题的思路就是用两个指针代表滑动窗口，先右指针右移，直到不满足条件（有重复字符），再左指针右移直至满足条件，在此过程中每当满足条件时更新字串的长度，直至右指针到达边界后结束
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
| #include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char,int> window;
int left=0,right=0,len=0;
while (right<s.size()){
char c=s[right];
right++;
while (window[c]){
char l=s[left];
window[l]--;
left++;
}
window[c]++;
if(len<right-left)
len=right-left;
}
return len;
}
};
|
wechat
alipay
