76. 最小覆蓋子串
給你一個字符串 s 玻孟、一個字符串 t 翩腐。返回 s 中涵蓋 t 所有字符的最小子串冕臭。如果 s 中不存在涵蓋 t 所有字符的子串晋被，則返回空字符串 "" 。
注意：如果 s 中存在這樣的子串翎卓，我們保證它是唯一的答案泪掀。
- 滑動窗口
附上討論區(qū)一篇講得很好理解的題解：簡簡單單，非常容易理解的滑動窗口思想
class Solution {
public String minWindow(String s, String t) {
//需求的字符個數(shù)
int count = t.length();
//need數(shù)組記錄窗口中的字符垃环，以及每個字符被需要的數(shù)量
//英文字母的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]--;
//如果窗口中已經(jīng)包含所有字符
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向右移動后窗口肯定不能滿足了 重新開始循環(huán)
need[s.charAt(l)]++;
l++;
count++;
}
r++;
}
return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
}
}
