学习记录算法滑动窗口
TONG HUI滑动窗口算法代码框架
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
| void slidingWindow(string s){
Map<Character,Integer> window = new HashMap();
int left = 0,right = 0;
while(right < s.length()){
char c = s.charAt(right);
right++;
...
while(window needs shrink){
char d = s.charAt(left);
left++;
...
}
}
}
|
其中两处 ... 表示的更新窗口数据的地方，到时候写自己的逻辑。
这两个 ... 处的操作分别是扩大和缩小窗口的更新操作。
最小覆盖子串
滑动窗口算法的思路
- 我们在字符串
S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。 - 我们先不断地增加
right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。 - 此时，我们停止增加
right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。 - 重复第
2 和第 3 步，直到 right 到达字符串 S 的尽头。
- 初始状态：
- 增加 right，直到窗口 [left, right) 包含了 T 中所有字符：
- 现在开始增加 left，缩小窗口 [left, right)：
- 直到窗口中的字符串不再符合要求，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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| String minWindow(String s,String t){
if (s == null || s.length() == 0 || t == null ||t.length() == 0){
return "";
}
Map<Character,Integer> window = new HashMap();
Map<Character,Integer> need = new HashMap();
for(int i=0;i<t.length();i++){
char c = t.charAt(i);
if(need.containsKey(c)){
need.put(c,need.get(c)+1);
}else{
need.put(c,1);
}
}
int left = 0,right = 0;
int valid = 0;
int start =0,len = Integer.MAX_VALUE;
while(right < s.length()){
char c = s.charAt(right);
right++;
if(need.containsKey(c)){
if(window.containsKey(c)){
window.put(c,window.get(c)+1);
}else{
window.put(c,1);
}
if(window.get(c).equals(need.get(c))){
valid++;
}
}
while(valid == need.size()){
if(right - left < len){
start = left;
len = right - left;
}
char d = s.charAt(left);
left++;
if(need.containsKey(d)){
if(window.get(d).equals(need.get(d))){
valid--;
}
window.put(d,window.get(d)-1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start,start+len);
}
|
字符串排列
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
| boolean checkInclusion(String t,String s){
if (s1.length() > s2.length()) {
return false;
}
Map<Character,Integer> window = new HashMap();
Map<Character,Integer> need = new HashMap();
for(int i=0;i<s1.length();i++){
char c = s1.charAt(i);
if(need.containsKey(c)){
need.put(c,need.get(c)+1);
}else{
need.put(c,1);
}
}
int left = 0,right = 0;
int valid = 0;
while(right < s2.length()){
char c = s2.charAt(right);
right++;
if(need.containsKey(c)){
if(window.containsKey(c)){
window.put(c,window.get(c)+1);
}else{
window.put(c,1);
}
if(window.get(c).equals(need.get(c))){
valid++;
}
}
while(right - left == s1.length()){
if(valid == need.size()){
return true;
}
char d = s2.charAt(left);
left++;
if(need.containsKey(d)){
if(window.get(d).equals(need.get(d))){
valid--;
}
if(window.containsKey(d)){
window.put(d,window.get(d)-1);
}
}
}
}
return false;
}
|
- 移动
left 缩小窗口的时机是窗口大小大于 t.size() 时，因为排列,长度应该是一样的。 - 当
valid == need.size() 时，就说明窗口中就是一个合法的排列，所以立即返回 true。 - 由于这道题中
[left, right) 其实维护的是一个定长的窗口，窗口大小为 t.size()。因为定长窗口每次向前滑动时只会移出一个字符，所以可以把内层的 while 改成 if，效果是一样的。
找所有字母异位词
输入一个串 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| List<Integer> findAnagrams(String s,String p){
if(p.length()>s.length()){
return new ArrayList();
}
Map<Character,Integer> window = new HashMap();
Map<Character,Integer> need = new HashMap();
for(int i=0;i<p.length();i++){
char c = p.charAt(i);
if(need.containsKey(c)){
need.put(c,need.get(c)+1);
}else{
need.put(c,1);
}
}
int left =0,right =0,valid =0;
List<Integer> res = new ArrayList();
while(right < s.length()){
char c = s.charAt(right);
right++;
if(need.containsKey(c)){
if(window.containsKey(c)){
window.put(c,window.get(c)+1);
}else{
window.put(c,1);
}
if(window.get(c).equals(need.get(c))){
valid++;
}
}
while(right - left >= p.length()){
if(valid == need.size()){
res.add(left);
}
char d = s.charAt(left);
left++;
if(need.containsKey(d)){
if(window.get(d).equals(need.get(d))){
valid--;
}
window.put(d,window.get(d)-1);
}
}
}
return res;
}
|
最长无重复子串
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
| int lengthOfLongestSubstring(String s){
Map<Character,Integer> window = new HashMap();
int left = 0,right =0,res =0;
while(right < s.length()){
char c = s.charAt(right);
right++;
if(window.containsKey(c)){
window.put(c,window.get(c)+1);
}else{
window.put(c,1);
}
while(window.get(c) > 1){
char d = s.charAt(left);
left++;
window.put(d,window.get(d)-1);
}
res = Math.max(res,right - left);
}
return res;
}
|
当 window[c] 值大于 1 时，说明窗口中存在重复字符，不符合条件，就该移动 left 缩小窗口了嘛。
