原题
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
示例:
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：
- 如果 S 中不存这样的子串，则返回空字符串
""。 - 如果 S 中存在这样的子串，我们保证它是唯一的答案。
解法
思想
滑动窗口，用一个hashmap存储原字符串中字符的出现个数，再用一个hashmap存储滑动窗口内目标字符的出现个数，用一个变量记录滑动窗口内有多少个字符满足条件了。
代码
class Solution {
public String minWindow(String s, String t) {
int left = 0, right = 0;
int start = 0, end = Integer.MAX_VALUE;
Map<Character, Integer> window = new HashMap();
Map<Character, Integer> needMap = new HashMap();
for(int i = 0; i < t.length(); i++) {
needMap.put(t.charAt(i), needMap.getOrDefault(t.charAt(i), 0) + 1);
}
int match = 0;
while(right < s.length()) {
char rightTemp = s.charAt(right);
if(needMap.containsKey(rightTemp)) {
int newCount = window.getOrDefault(rightTemp, 0) + 1;
window.put(rightTemp, newCount);
if(newCount == needMap.getOrDefault(rightTemp, 0)){
match++;
}
}
right++;
while(match == needMap.size()) {
if(right - left < end - start) {
start = left;
end = right;
}
char leftTemp = s.charAt(left);
if(needMap.containsKey(leftTemp)) {
window.put(leftTemp, window.getOrDefault(leftTemp, 0) - 1);
if(window.getOrDefault(leftTemp, 0) < needMap.getOrDefault(leftTemp, 0)) {
match--;
}
}
left++;
}
}
return end == Integer.MAX_VALUE ? "" : s.substring(start, end);
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode76-%e6%9c%80%e5%b0%8f%e8%a6%86%e7%9b%96%e5%ad%90%e4%b8%b2/
