最近在整理之前刷过的leetcode题目，想写写一些常见的、典型的解题技巧或者方法。最开始刷题的时候，总觉得题目好难，其实刷多了题，也就那么回事😆。这篇博客主要想介绍一下滑动窗口方法(sliding window)，对于解决字符串问题非常有用🤩～
这一篇解答写的非常的透彻，详细请参看链接：滑动窗口思想
滑动窗口，主要是用来解决子串问题。一般的解决思路是：首先，我们定义left与right两个标志，用来界定滑动窗口的左右边界；接着，我们不断地移动右边界，即right++；当满足某一条件之后，我们不断地移动左边界，即left++，缩减滑动窗口的大小，直到满足最后的条件，然后返回结果。下面以leetcode上的三道题为例：
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
|
#include<stdio.h>
#include<string.h>
#include<string>
#include<vector>
#include<unordered_set>
#include<iostream>
#include<unordered_map>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size()==0) return 0;
int left=0,right=0;
unordered_map<char,int> m;
int maxsize=0;
while(right<s.size()){
char c1=s[right];
m[c1]++;
right++;
while(m[c1]>1){
char c2=s[left];
m[c2]--;
left++;
}
maxsize=max(maxsize,right-left);
}
return maxsize;
}
};
int main(){
string s;
cin>>s;
Solution so1;
int ans=so1.lengthOfLongestSubstring(s);
printf("%d\n",ans);
return 0;
}
|
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
68
69
70
71
72
73
74
75
76
77
78
|
#include<stdio.h>
#include<string.h>
#include<string>
#include<vector>
#include<unordered_map>
#include<algorithm>
#include<iostream>
using namespace std;
class Solution{
public:
string minWindow(string s, string t) {
if(t.size()==0 || s.size()==0) return "";
unordered_map<char,int> m_t;
unordered_map<char,int> window;
for(int i=0;i<t.size();i++) m_t[t[i]]++;
int left=0,right=0;
int start=0,minlen=INT_MAX;
int match=0;
while(right<s.size()){
char c1=s[right];
if(m_t.count(c1)){
window[c1]++;
if(window[c1]==m_t[c1]){
match++;
}
}
right++;
while(match==m_t.size()){
char c2=s[left];
if(right-left<minlen){
start=left;
minlen=right-left;
}
if(m_t.count(c2)){
window[c2]--;
if(window[c2]<m_t[c2]){
match--;
}
}
left++;
}
}
return minlen==INT_MAX?"":s.substr(start,minlen);
}
};
int main(){
string s,t;
cin>>s>>t;
Solution so1;
string ans=so1.minWindow(s,t);
cout<<ans<<endl;
return 0;
}
|
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
#include<stdio.h>
#include<string.h>
#include<string>
#include<vector>
#include<algorithm>
#include<iostream>
#include <set>
#include<unordered_map>
using namespace std;
class Solution{
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ans;
if(s.size()==0) return ans;
unordered_map<char,int> m_p;
unordered_map<char,int> window;
int left=0,right=0;
int match=0;
for(int i=0;i<p.size();i++) m_p[p[i]]++;
while(right<s.size()){
char c1=s[right];
if(m_p.count(c1)){
window[c1]++;
if(window[c1]==m_p[c1]){
match++;
}
}
right++;
while(match==m_p.size()){
char c2=s[left];
if(right-left==p.size()){
ans.push_back(left);
}
if(m_p.count(c2)){
window[c2]--;
if(window[c2]<m_p[c2]){
match--;
}
}
left++;
}
}
return ans;
}
};
int main(){
string s,p;
cin>>s>>p;
Solution so1;
vector<int> ans=so1.findAnagrams(s,p);
for(int i=0;i<ans.size();i++){
printf("%d ",ans[i]);
}
printf("\n");
return 0;
}
|
具体代码应该很清楚啦，over☕️～
