leetcode 76. 最小覆盖子串
用滑动窗口来解答此题，有几个关键点：
一、确认整个遍历操作中我们需要用到的变量
- left、right 就不用说了，在滑动窗口类的题目这两个变量基本必有；
- needs 哈希桶，用来表示目标字符串的各个字符以及各个字符要求出现的次数；
- windows 哈希桶，用来表示当前窗口中符合的字符，以及字符出现次数；
- start、len 分别用来实时标记最小子串的开始索引，以及其长度；
- validCount 用来记录当前窗口中满足”目标字符串字符出现的次数”的个数（有点绕。。书面表达是个硬伤T T）
二、确定左边窗口何时向右收敛
- 答案就是在右边窗口挪动时找到一对符合要求的子串时，就需要通过移动左边窗口，来尝试获取长度更小的符合要求的子串。
三、各个变量在何时被维护？仔细想想，有几个关键时刻：
1、右边窗口往右滑动：
- 如果碰到了目标字符串中的字符，我们需要维护什么变量？主要就是要维护当前窗口目标字符hash桶中的计数器；
- 如果碰到了目标字符串中的字符，而且在维护完hash桶计数器后，发现与目标字符要求出现次数相同，那么我们就认为有一个目标字符满足了出现次数的要求，让validCount加1。
2、每次窗口中字符满足覆盖要求时：
- 试算一下当前窗口的长度是否比以往更小，是则需要更新最小子串的开始索引以及其长度；
- 同时，虽然本次窗口中的字符已经满足覆盖要求，但如果我们把左边窗口往右边收敛，是不是有可能获取到一个更短但也满足覆盖要求的子串？所以我们就尝试左边窗口向右收敛；
- 在向右收敛的过程中，如果（条件1 ）本次剔除的最左边的字符刚好是目标字符串中的字符，我们就再判断下是不是（条件2）失去这个字符后不再满足覆盖要求，如果条件1与2都符合的话就要让validCount减1，而不管符不符合条件2，只要满足条件1我们都要让当前窗口字符对应的计数器减1。
最终返回目标子串即可。
某一时刻的窗口快照.png
代码实现如下：
public class Solution {
public String minWindow(String s, String t) {
// 用以记录需要的字符以及每个字符应该出现次数
Map<Character, Integer> needs = new HashMap<>();
for(int i = 0; i < t.length(); i++) {
char c = t.charAt(i);
needs.put(c, needs.getOrDefault(c, 0) + 1);
}
// 用以记录当前窗口中符合needs的字符以及每个字符出现的次数
Map<Character, Integer> windows = new HashMap<>();
// 滑动窗口的左右窗口，左闭右开[left,right)
int left = 0, right = 0;
// 用来记录结果：子串的开始索引以及长度
int start = 0, len = Integer.MAX_VALUE;
// 记录当前窗口中字符出现次数满足needs要求的个数，只有当全部字符出现个数都满足了，左窗口才尝试向右收缩
int validCount = 0;
while (right < s.length()) {
// 往右滑动
char c = s.charAt(right++);
// 找到一个需要的字符
if (needs.containsKey(c)) {
// 当前窗口统计该字符的hash桶计数器+1
windows.put(c, windows.getOrDefault(c, 0) + 1);
// 出现的次数刚好达到要求
if (windows.get(c).equals(needs.get(c))) {
// 表示当前窗口中，当前字符的出现次数已达到要求
validCount++;
}
}
// 所有字符的出现字数都满足了，那么准备左边窗口向前收缩（尝试圈一个更小的子串）
while (validCount == needs.size()) {
// 每次达到字符数要求，就试图更新一下字串开始索引与长度
if (right - left < len) {
start = left;
len = right - left;
}
// 左边窗口向前收缩
char l = s.charAt(left++);
// 如果收缩前最左边的字符为需要的字符，那么更新当前窗口完成的字符个数，并更新窗口中有效字符个数
if (needs.containsKey(l)) {
// 右移去掉该字符后，出现次数达不到要求，那么符合needs要求的个数要减1
if (windows.get(l).equals(needs.get(l))) {
validCount--;
}
windows.put(l, windows.get(l) - 1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
}
网友评论