力扣76 最小覆盖子串
给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。
这道题利用滑动窗口来解答。滑动窗口算法技巧主要用来解决子数组问题，比如让你寻找符合某个条件的最长/最短子数组。
*参考labuladong的算法笔记来总结。
通过学习滑动窗口的框架来解决子串，子数组的问题。
遇到子串/子数组相关的题目，我们只需要回答以下三个问题，只要能回答这三个问题，就说明可以使用滑动窗口技巧解题。
1、什么时候应该移动 right 扩大窗口？窗口加入字符时，应该更新哪些数据？
2、什么时候窗口应该暂停扩大，开始移动 left 缩小窗口？从窗口移出字符时，应该更新哪些数据？
3、什么时候应该更新结果？
根据这道题，我们具体回答这三个问题。
首先，准备两个哈希表（字典）：
need：记录t中每个字符需要多少个（比如t="ABC"，need={'A':1,'B':1,'C':1}）window：记录当前窗口里，每个字符实际有多少个
再单独用一个变量valid（就是 window 计数）：代表已经满足数量要求的字符种类数。
1. 什么时候移动 right 扩大窗口？
只要valid < need里字符种类总数，就持续右移 right，把字符纳入窗口。 加入字符时： 如果这个字符正好在need里面，就给window[该字符] += 1； 更新完之后，如果window[该字符] == need[该字符]，说明这个字符达标了，valid +=1。
2. 什么时候暂停扩大，移动 left 缩小窗口？
当 valid == need.size ( )（窗口已经完整覆盖 t），停止扩大，开始尝试收缩 left，寻找更短的合法子串。 移出 left 字符的时候： 如果这个字符在need里，先判断window[该字符] == need[该字符]，如果是的话，说明一旦删掉它，这个字符就不满足了，valid -=1； 然后再执行window[该字符] -=1。 一直缩小，直到 valid < need.size()，窗口不再满足覆盖条件，停止收缩。
3. 什么时候更新结果？
只要窗口处于合法状态（valid == need.size ( )）的期间，每一轮收缩 left 之前，都要更新一次结果。 因为此时窗口是合法的，我们要对比当前窗口长度，保留最短的那一个。 不是只在刚找到合法窗口更新一次，收缩的每一步只要窗口还合法，都要更新，因为 left 不断右移，窗口在变短，有可能找到更小的。
下面是完整代码：
class Solution {
public String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
// 记录最小覆盖子串的起始索引及长度
int start = 0, len = Integer.MAX_VALUE;
while (right < s.length()) {
// c 是将移入窗口的字符
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;
}
// d 是将移出窗口的字符
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.前置准备
构建need哈希表，统计目标字符串t所需要每个字符的数量；
初始化window哈希表，记录当前目标字符的数量；
定义变量left，valid（满足数量要求的字符种类数），记录答案的变量（start，len）
2.外层for循环：移动right扩大窗口
for (int right = 0; right < s.length(); right++) {
// 移入窗口的字符c：s[right]
char c = s.charAt(right);
// 如果c是我们需要的字符（need包含这个key）
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c,0)+1);
// 当窗口内c的数量刚好等于need要求数量 → 这个字符种类达标，valid+1
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
// 窗口是否已经满足条件，满足就进入循环缩小left（回答问题2）
while (valid == need.size()) {
// 回答问题3：窗口合法，更新结果（记录最优解）
if (right - left < len) {
start = left;
len = right - left;
}
// 开始移动left，缩小窗口
char d = s.charAt(left); // 要移出窗口的字符
left++;
// 移出的字符d如果是目标字符，更新window、valid
if (need.containsKey(d)) {
// 如果移出前刚好等于需要的数量，移走之后就不达标了，valid--
if (window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.get(d)-1);
}
}
}
遇到其他滑动窗口子串题，框架基本不动，只用修改need的构建和while收缩窗口的条件
补充题： 567 力扣-字符串的排列
转载自 CSDN-专业IT技术社区
