题目

输入两个字符串s和t，请找出字符串s中包含字符串t的所有字符的最短子字符串。例如，输入的字符串s为"ADDBANCAD"，字符串t为"ABC"，则字符串s中包含字符’A’、'B’和’C’的最短子字符串是"BANC"。如果不存在符合条件的子字符串，则返回空字符串""。如果存在多个符合条件的子字符串，则返回任意一个。

分析

如果某一时刻两个指针之间的子字符串还没有包含字符串t的所有字符，则在子字符串中添加新的字符，于是向右移动第2个指针。如果仍然没有包含字符串t的所有字符，则继续向右移动第2个指针。
如果某一时刻两个指针之间的子字符串已经包含字符串t的所有字符，由于目标是找出最短的符合条件的子字符串，因此向右移动第1个指针，以判断删除子字符串最左边的字符之后是否仍然包含字符串t的所有字符。

解

public class Test {public static void main(String[] args) {String result = minWindow("ADDBANCAD","ABC");System.out.println(result);}public static String minWindow(String s, String t) {HashMap<Character, Integer> charToCount = new HashMap<>();for (char ch : t.toCharArray()) {charToCount.put(ch, charToCount.getOrDefault(ch, 0) + 1);}// count是t字符串去重后的数量int count = charToCount.size();// start,end是遍历的两个指针；minStart,minEnd是记录长度最小时的两个指针int start = 0, end = 0, minStart = 0, minEnd = 0;int minLength = Integer.MAX_VALUE;// 没有遍历完 或 遍历完了且符合条件 进这个循环while (end < s.length() || (count == 0 && end == s.length())) {if (count > 0) {// 没符合条件char endCh = s.charAt(end);if (charToCount.containsKey(endCh)) {charToCount.put(endCh, charToCount.get(endCh) - 1);if (charToCount.get(endCh) == 0) {// 因为count是去重后的个数count--;}}end++;}else {// 符合条件了继续往后遍历最小值if (end - start < minLength) {minLength = end - start;minStart = start;minEnd = end;}char startCh = s.charAt(start);if (charToCount.containsKey(startCh)) {charToCount.put(startCh, charToCount.get(startCh) + 1);if (charToCount.get(startCh) == 1) {// 因为count是去重后的个数，现在等于1，说明原来是0，新增个数了count++;}}start++;}}return minLength < Integer.MAX_VALUE ? s.substring(minStart, minEnd) : "";}
}