0076.Minimum Window Substring
给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。
示例：
1
2
| 输入：S = "ADOBECODEBANC", T = "ABC"
输出："BANC"
|
提示：
- 如果 S 中不存这样的子串，则返回空字符串
""。
- 如果 S 中存在这样的子串，我们保证它是唯一的答案。
解题思路
这题在 0003 题中就已经提过了的暗号，就是洒洒水的使用一下 Sliding Window 就可以了，思路还是比较简单的：先不断的扩张窗口右边，直到将所有的要包含的短字符串；然后开始就移动窗口的左边，直到左边压缩到不能再容纳这个短字符串了，再进行不断比较，就可以得到最终结果了。
这种时候就需要出现 但是 这个词语，果然在实现的时候就需要注意很多问题了，对于这种抽象问题，先来个🌰：给的例子实在是太普通了，应该用那种带点特殊性的例子
S = “ABANCDB” T = “ABC”
对着代码捋一遍应该就懂了：
第一遍过后可以看见：”ABANC” 是一个滑动窗口，map 的值也变为了：
|
A |
B |
C |
| 初始值 |
1 |
1 |
1 |
| 遍历到 A |
0 |
1 |
1 |
| 遍历到 B |
0 |
0 |
1 |
| 遍历到 A |
-1 |
0 |
1 |
| 遍历到 N |
-1 |
0 |
1 |
| 遍历到 C |
-1 |
0 |
0 |
此时的 count == t 的长度了，这样扩张窗口就完成了 ======> min = 5
接下来就是收缩窗口，其根本原因就是这样左边出现重复元素，可以去掉形成最小的窗口：
如果在 map 中的值是等于 0 的，说明它是刚刚好的，如果把这个排除的话，这个窗口就不再成立了，要继续扩张
窗口了；如果 map 中的值 小于 0 的，说明它是多余的，但是要看它的位置了，可以看下🌰：
“ABANC” 这个 A 就可以去掉；”BAANC” 这个 A 就不可以去掉，此时就要扩张窗口了
反复横跳 ，完成✅
代码
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
| class Solution {
public String minWindow(String s, String t) {
Map<Character, Integer> map = new HashMap<>();
for(int i = 0; i < t.length(); i++) {
char c = t.charAt(i);
if (map.containsKey(c)) {
int tmp = map.get(c);
map.put(c, tmp + 1);
}
else {
map.put(c, 1);
}
}
int count = 0;
int left = 0, right = 0;
int min = Integer.MAX_VALUE;
int minLeft = 0, minRight = 0;
for (; right < s.length(); right++) {
char temp = s.charAt(right);
if (map.containsKey(temp)) {
count = map.get(temp) > 0 ? count + 1 : count;
map.put(temp, map.get(temp) - 1);
}
while (count == t.length()) {
if ((right - left) < min) {
min = right - left;
minLeft = left;
minRight = right;
}
char c = s.charAt(left);
if (map.containsKey(c)) {
if (map.get(c) >= 0)
count--;
map.put(c, map.get(c) + 1);
}
left++;
}
}
return min == Integer.MAX_VALUE ? "" : s.substring(minLeft, minRight + 1);
}
}
|