76. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
- 滑动窗口
附上讨论区一篇讲得很好理解的题解：简简单单，非常容易理解的滑动窗口思想
class Solution {
public String minWindow(String s, String t) {
//需求的字符个数
int count = t.length();
//need数组记录窗口中的字符，以及每个字符被需要的数量
//英文字母的ASCII码值范围a-z：97-122；A-Z：65-90
int[] need = new int[123];
for (int i = 0; i < t.length(); i++) {
need[t.charAt(i)]++;
}
//size记录窗口大小，start是最小覆盖串开始的index
int size = Integer.MAX_VALUE, start = 0;
//窗口左右边界
int l = 0, r = 0;
while (r < s.length()) {
char c = s.charAt(r);
//需要字符c
if (need[c] > 0) {
count--;
}
//把右边的字符加入窗口
need[c]--;
//如果窗口中已经包含所有字符
if (count == 0) {
while (l < r && need[s.charAt(l)] < 0) {
//左指针右移，并释放移动出窗口的字符（不被需要的字符）
need[s.charAt(l)]++;
l++;
}
//遇到需要的字符时左指针停止右移，更新最小窗口
if (r - l + 1 < size) {
size = r - l + 1;
start = l;
}
//l向右移动后窗口肯定不能满足了 重新开始循环
need[s.charAt(l)]++;
l++;
count++;
}
r++;
}
return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
}
}
