一、滑动窗口解题框架
滑动窗口算法技巧很简单，但是具体怎么进行滑动比较难。一般的逻辑都是：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
int left = 0, right = 0;
while (right < s.size()) {
// 增大窗口
window.add(s[right]);
right++;
while (window needs shrink) {
// 缩小窗口
window.remove(s[left]);
left++;
}
}
|
算法的时间复杂度为 O(N)，遍历一趟就ok。
滑动窗口算法的代码框架如下：
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
|
// 滑动窗口算法框架
void slidingWindow(String s, String t) {
HashMap<Character, Integer> need = new HashMap<>();
HashMap<Character, Integer> window = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
char c = t.charAt(i);
need.put(c, need.getOrDefault(c, 0) + 1);
}
// 左闭右开
int left = 0, right = 0;
int valid = 0;
while (right < s.length) {
// c 是将移入窗口的字符
char c = s.charAt(right);
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/
System.out.println("window: [", left, ",", right, "]");
/***********************/
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s.charAt(left);
// 左移窗口
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
|
class Solution {
public String minWindow(String s, String t) {
HashMap<Character, Integer> need = new HashMap<>();
HashMap<Character, Integer> window = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
char c = t.charAt(i);
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int start = 0, len = Integer.MAX_VALUE;
int valid = 0;
while (right < s.length()) {
char c = s.charAt(right);
right++;
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 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
|
class Solution {
public boolean checkInclusion(String s1, String s2) {
HashMap<Character, Integer> need = new HashMap<>();
HashMap<Character, Integer> window = new HashMap<>();
for (int i = 0; i < s1.length(); i++) {
char c = s1.charAt(i);
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
while (right < s2.length()) {
char c = s2.charAt(right);
right++;
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 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--;
window.put(d, window.get(d) - 1);
}
}
}
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
28
29
30
31
32
33
34
|
class Solution {
public List<Integer> findAnagrams(String s, String p) {
HashMap<Character, Integer> need = new HashMap<>();
HashMap<Character, Integer> window = new HashMap<>();
for (int i = 0; i < p.length(); i++)
need.put(p.charAt(i), need.getOrDefault(p.charAt(i), 0) + 1);
int left = 0, right = 0;
int valid = 0;
ArrayList<Integer> res = new ArrayList<>();
while (right < s.length()) {
char c = s.charAt(right);
right++;
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c)))
valid++;
}
while (right - left >= p.length()) {
if (valid == need.size()) {
res.add(left);
// System.out.println(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
|
class Solution {
public int lengthOfLongestSubstring(String s) {
HashSet<Character> window = new HashSet<>();
int left = 0, right = 0;
int valid = 1;
int res = 0;
while (right < s.length()) {
char c = s.charAt(right);
right++;
if (window.contains(c)) {
valid = 0;
} else {
window.add(c);
}
while (valid == 0) {
char d = s.charAt(left);
left++;
if (c == d)
valid = 1;
else
window.remove(d);
}
res = Math.max(res, right - left);
}
return res;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public int maxPower(String s) {
int res = 1;
int n = s.length();
int left = 0, right = 0;
while (right < n) {
char c = s.charAt(right);
right++;
while(s.charAt(left) != c) {
left++;
}
res = Math.max(res, right - left);
}
return res;
}
}
|