链接：https://leetcode-cn.com/problems/minimum-window-substring/
标签：哈希表、字符串、滑动窗口
题目
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2：
输入：s = "a", t = "a"
输出："a"
提示：
- 1 <= s.length, t.length <= 105
- s 和 t 由英文字母组成
进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？
分析
如果要在O(n)时间内解决此题，那么循环肯定是不行的，所以此题使用滑动窗口来解决，也是双指针的一种题型。
思路就是：
（1）使用两个指针left、right，初始left = right = 0。[left, right)称为一个窗口。
（2）right不断右移寻找目标字符放入窗口序列中，直到窗口序列全部包含目标字符。
（3）left右移，把字符从窗口序列中移除，直到窗口序列不包含目标子串，此时得到一个最短的目标子串。
（4）重复（2）（3）两步，不断更新最短目标子串，直到right到达字符串末尾。
其实第（2）步相当于找到了一个可行解，第（3）步就是找到一个最优解。
综上，我们需要用到的几个变量是：双指针left和right，窗口序列window，目标序列need，记录最短目标子串的长度。其他的按需增加。
编码
class Solution {
public String minWindow(String s, String t) {
// 目标字符数组
Map<Character, Integer> need = new HashMap<>();
// 窗口数组
int[] window = new int[128];
// valid已找到的字符数
int left = 0, right = 0, valid = 0;
// 最小子串的长度
int len = Integer.MAX_VALUE;
// 最小子串的起始下标
int start = 0;
for (int i = 0; i < t.length(); i++) {
need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
}
// 右指针往右走
while (right < s.length()) {
char c = s.charAt(right);
right++;
// 说明这个字符包含在目标字符串中
if (need.containsKey(c)) {
window[c]++;
// 找到了一个满足条件的字符（数量够了）
if (window[c] == need.get(c)) {
valid++;
}
}
// 所有的目标字符都已经找到，缩小窗口寻找最小子串
while (valid == need.size()) {
// 更新起始下标和最小子串的长度
if (right - left < len) {
len = right - left;
start = left;
}
// 移出窗口的元素
char d = s.charAt(left);
left++;
if (need.containsKey(d)) {
if (need.get(d) == window[d]) {
valid--;
}
window[d]--;
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
}
image-20210705210921491.png
