最小覆盖子串
滑动窗⼝算法的思路是这样：
- 在字符串 S 中使⽤双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为⼀个「窗⼝」
- 先不断地增加 right 指针扩⼤窗⼝ [left, right]，直到窗⼝中的字符串 符合要求（包含了 T 中的所有字符）。
- 此时，停⽌增加 right，转⽽不断增加 left 指针缩⼩窗⼝ [left, right]，直到窗⼝中的字符串不再符合要求（不包含 T 中的所有字符了）。 同时，每次增加 left，都要更新⼀轮结果。
- 重复第 2 和第 3 步，直到 right 到达字符串 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
30
31
32
33
34
35
36
37
static String minWindow(String s, String t) {
// 记录最短⼦串的开始位置和⻓度
int start = 0, minLen = Integer.MAX_VALUE;
int left = 0, right = 0;
Map<Character, Integer> window = new HashMap<>();
Map<Character, Integer> needs = new HashMap<>();
for (char c : t.toCharArray()) {
needs.put(c, needs.getOrDefault(c, 0) + 1);
}
int match = 0;
while (right < s.length()) {
char c1 = s.charAt(right);
if (needs.containsKey(c1)) {
window.put(c1, window.getOrDefault(c1, 0) + 1);
if (window.getOrDefault(c1, 0).equals(needs.getOrDefault(c1, 0)))
match++;
}
right ++;
while (match == needs.size()) {
if (right - left < minLen) {
// 更新最⼩⼦串的位置和⻓度
start = left;
minLen = right - left;
}
char c2 = s.charAt(left);
if (needs.containsKey(c2)) {
window.put(c2, window.getOrDefault(c2, 0) - 1);
if (window.getOrDefault(c2, 0) < needs.getOrDefault(c2, 0))
match--;
}
left++;
}
}
return minLen == Integer.MAX_VALUE ?
"" : s.substring(start, start + minLen);
}
这个算法的时间复杂度是 O(M + N)，M 和 N 分别是字符串 S 和 T 的⻓度。因为先⽤ for 循环遍历了字符串 T 来初始化 needs，时间 O(N)，之后的两个 while 循环最多执⾏ 2M 次，时间 O(M)。
找到字符串中所有字⺟异位词
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
static List<Integer> findAnagrams(String s, String t) {
// ⽤数组记录答案
List<Integer> res = new ArrayList<>();
int left = 0, right = 0;
Map<Character, Integer> needs = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray())
needs.put(c, needs.getOrDefault(c, 0) + 1);
int match = 0;
while (right < s.length()) {
char c1 = s.charAt(right);
if (needs.containsKey(c1)) {
window.put(c1, window.getOrDefault(c1, 0) + 1);
if (window.get(c1).equals(needs.get(c1)))
match++;
}
right++;
while (match == needs.size()) {
// 如果 window 的⼤⼩合适
// 就把起始索引 left 加⼊结果
if (right - left == t.length()) {
res.add(left);
}
char c2 = s.charAt(left);
if (needs.containsKey(c2)) {
window.put(c2, window.getOrDefault(c2, 0) - 1);
if (window.getOrDefault(c2, 0) < needs.getOrDefault(c2, 0))
match--;
}
left++;
}
}
return res;
}
⽆重复字符的最⻓⼦串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int lengthOfLongestSubstring(String s) {
int left = 0, right = 0;
Map<Character, Integer> window = new HashMap<>();
int res = 0; // 记录最⻓⻓度
while (right < s.length()) {
char c1 = s.charAt(right);
window.put(c1, window.getOrDefault(c1, 0) + 1);
right++;
// 如果 window 中出现重复字符
// 开始移动 left 缩⼩窗⼝
while (window.getOrDefault(c1, 0) > 1) {
char c2 = s.charAt(left);
window.put(c2, window.getOrDefault(c2, 0) - 1);
left++;
}
res = Math.max(res, right - left);
}
return res;
}
遇到⼦串问题，⾸先想到的就是滑动窗⼝技巧。
总结
可以总结出滑动窗⼝算法的抽象思想：
1
2
3
4
5
6
7
8
9
int left = 0, right = 0;
while (right < s.size()) {
window.add(s[right]);
right++;
while (valid) {
window.remove(s[left]);
left++;
}
}
其中 window 的数据类型可以视具体情况⽽定，⽐如上述题⽬都使⽤哈希表充当计数器，当然也可以⽤⼀个数组实现同样效果，因为只处理英⽂字⺟。
