模板
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
|
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()) {
char c = s[right];
right++;
...
while (window needs shrink) {
char d = s[left];
left++;
...
}
}
}
|
最长不含重复字符的子字符串
朴素的想法：
无非就是双指针，一个指向前，一个指向后，用一个hash表记录碰到的字符出现的次数，如果字符出现的次数变为了2，那么左指针就要一直移动直到消除这个碰到的字符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char,int>window;
int left = 0,right = 0;
int maxl = 0;
while(right < s.length()){
char c = s[right];
window[c]++;
right++;
while(window[c]>1){
window[s[left]]--;
left++;
}
maxl = max(maxl,right-left);
}
return maxl;
}
};
|
最小覆盖子串
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) {
unordered_map<char,int>need,window;
for(char c: t)need[c]++;
int left = 0,right = 0;
int needCnt = need.size();
int minl = INT_MAX,start = 0;
while(right < s.length()){
char c = s[right];
right++;
if(need.count(c) > 0){
window[c]++;
if(window[c] == need[c]){
needCnt--;
}
}
while(needCnt == 0){
if(minl > right - left){
start = left;
minl = right - left;
}
char d = s[left];
left++;
if(need.count(d) > 0){
if(window[d] == need[d])
needCnt++;
window[d]--;
}
}
}
return minl == INT_MAX ? "" : s.substr(start,minl);
}
|
字符串的排列
window滑动窗口的双指针更新操作如下：
- right指针一直加1
- 如果碰到了需要的字符(s[right]在need子串之中)，那么更新window窗口数组（
window[s[right]]++且判断是否needCnt--）
- 如果window窗口数组满足条件，left++直到window不再满足条件（
window[s[left]]--且判断是否needCnt++，期间可以更新最短的覆盖子串的长度等各种信息）
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
| class Solution {
public:
bool checkInclusion(string s1, string s2) {
unordered_map<char,int>need,window;
for(char c : s1)need[c]++;
int needCnt = need.size();
int left = 0,right = 0;
while(right < s2.length()){
char c = s2[right];
right++;
if(need.count(c) > 0){
window[c]++;
if(window[c] == need[c])
needCnt--;
}
while(needCnt == 0){
if(right-left == s1.size())return true;
char d = s2[left];
left++;
if(need.count(d) > 0){
window[d]--;
if(window[d]<need[d])needCnt++;
}
}
}
return false;
}
};
|
至多包含两个不同字符串的最长子串
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
| class Solution {
public:
int lengthOfLongestSubstringTwoDistinct(string s) {
unordered_map<char,int>windows;
int left = 0,right = 0;
int cnt = 0;
int maxl = 0;
while(right < s.length()){
char c = s[right];
right++;
if(windows.count(c) == 0||windows[c] == 0)
cnt++;
windows[c]++;
while(cnt == 3){
char d = s[left];
windows[d]--;
if(windows[d] == 0)cnt--;
left++;
}
if(cnt <= 2)maxl = max(maxl,right - left);
}
return maxl;
}
};
|
找到字符串中所有的字母异位词
window滑动窗口的双指针更新操作如下：
- right指针一直加1
- 如果碰到了需要的字符(s[right]在need子串之中)，那么更新window窗口数组（
window[s[right]]++且判断是否needCnt--）
注意判断是否needCnt–最稳妥的方法就是window[c] == need[c]的时候，即务必使用==
- 如果window窗口数组满足条件，left++直到window不再满足条件（
window[s[left]]--且判断是否needCnt++，期间可以更新最短的覆盖子串的长度等各种信息）
注意判断是否needCnt++最稳妥的方法就是window[d] == need[d]的时候，即务必使用==
总而言之，滑动窗口题目的样式十分固定，仅需注意一些细节以及更新结果的位置，结果更新的位置可能在while循环前面可能在window满足条件时更新，也可能在最后更新
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
| class Solution {
public:
vector<int> findAnagrams(string s, string p) {
unordered_map<char,int>need,window;
for(auto e : p)need[e]++;
int needCnt = need.size();
int left = 0,right = 0;
vector<int>results;
while(right < s.size()){
char c = s[right];
right++;
if(need.count(c)){
window[c]++;
if(window[c] == need[c])
needCnt--;
}
while(right - left > p.size()){
char d = s[left];
if(need.count(d)){
if(window[d] == need[d])needCnt++;
window[d]--;
}
left++;
}
if(needCnt == 0)results.push_back(left);
}
return results;
}
};
|
子数组的最大平均数
window滑动窗口的双指针更新操作如下：
- right指针一直加1
- 每次sum的值
+nums[right]
- 如果window窗口数组过于大了需要收缩，left++直到window再次满足条件sum的值每次
-nums[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
| class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
int left = 0,right = 0;
double maxd = -100000.0;
double sum = 0.0;
while(right < nums.size()){
double c = nums[right];
right++;
sum += c;
if(right - left == k)maxd = max(maxd,sum/k);
while(right - left >= k){
double d = nums[left];
sum -= d;
left++;
}
}
return maxd;
}
};
|
滑动窗口最大值
队列按从大到小放入：
- 如果首位值（即最大值）不在窗口区间，删除首位
- 如果新增的值小于队列尾部值，加到队列尾部
- 如果新增值大于队列尾部值，删除队列中比新增值小的值，如果在把新增值加入到队列中
- 如果新增值大于队列中所有值，删除所有，然后把新增值放到队列首位，保证队列一直是从大到小
队列移除：
- 如果移除的值恰好为队列首部元素，删除队列首部元素即可
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
| class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int left = 0,right = 0;
deque<int>dq;
vector<int>results;
while(right < nums.size()){
int c = nums[right];
right++;
while(!dq.empty()&&dq.back() < c){
dq.pop_back();
}
dq.push_back(c);
if(right - left == k){
int d = nums[left];
results.push_back(dq[0]);
if(dq.front() == d)
dq.pop_front();
left++;
}
}
return results;
}
};
|
