题目描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
提示：s 和 t 由英文字母组成
条件分析
- 不需要考虑字符顺序；
- t中的字符可能会重复，使用map来记录字符出现的频率；
- 要返回子串的具体内容，需要记住符合结果的起始位置；
解题思路（滑动窗口）
-
定义一个map，记录t中字符出现的次数，其中key为字符，count为次数；次数都为0时，代表匹配成功，为负数，代表存在多余的字符，为正数，代表存在还需要匹配的字符；
-
定义一个matchSize，代表出现字符匹配的数量，当且仅当元素存在且count为正数时（说明该元素待匹配），count--，matchSize++；
-
定义两个下标left,right，当right处的字符存在且count为正数时，更新matchSize，如果matchSize等于t的长度时，此时[left,right]是s的一个子串，且包含t中的所有内容；
-
3中的[left,right]中可能存在count为负数的情况，说明存在多余的字符，对left进行增加，并增加left所在元素count的值，当发现count恢复为正数时，left到达最右侧，此时[left,right]之间的字符最少，记录此时的left和right；
-
记录4中出现的下标，并重复3和4这个过程，即可找到最后的解；
编码如下
public String minWindow(String s, String t) {
int sLength = s.length();
int tLength = t.length();
if (sLength < tLength) {
return "";
}
Map<Character, Integer> tCharCountMap = new HashMap<>();
for (char c : t.toCharArray()) {
Integer count = tCharCountMap.get(c);
if (count == null) {
tCharCountMap.put(c, 1);
} else {
tCharCountMap.put(c, ++count);
}
}
char[] sCharArray = s.toCharArray();
int resultLeft = -1;
int resultRight = Integer.MAX_VALUE-1;
int left = 0;
int right = 0;
int matchSize = 0;
while(right < sLength) {
char rightChar = sCharArray[right];
Integer count = tCharCountMap.get(rightChar);
if (count != null) {
count--;
tCharCountMap.put(rightChar, count);
if (count >= 0) {
matchSize++;
if (matchSize == tLength) {
while (left <= right) {
Integer leftCharCount = tCharCountMap.get(sCharArray[left]);
if (leftCharCount != null) {
tCharCountMap.put(sCharArray[left], ++leftCharCount);
if (leftCharCount > 0) {
if (right - left < resultRight - resultLeft) {
resultLeft = left;
resultRight = right;
}
left++;
matchSize--;
break;
}
}
left++;
}
}
}
}
right++;
}
if (resultLeft == -1) {
return "";
}
return s.substring(resultLeft, resultRight+1);
}