LeetCode 76. 最小覆盖子串
思路：
准备一个map1记录字符串t（字符, 字符个数）准备一个map2记录在s的窗口中所包含的t串字符（字符，字符个数）左端点收缩条件：窗口内已经覆盖了t串class Solution {public static String minWindow(String s, String t) {// 记录tHashMap<Character, Integer> map1 = new HashMap<>();// 记录窗口中包含的t的元素HashMap<Character, Integer> map2 = new HashMap<>();// 记录最短的子串窗口边界下标int l = -1, r = -1;int minLen = s.length() + 1;// 初始化map1for (int i = 0; i < t.length(); i++) {map1.put(t.charAt(i), map1.getOrDefault(t.charAt(i), 0) + 1);}// 滑动窗口int start = 0;for (int end = 0; end < s.length(); end++) {// 往map2内放元素if (map1.containsKey(s.charAt(end))) {map2.put(s.charAt(end), map2.getOrDefault(s.charAt(end), 0) + 1);}// 左端点收缩条件:map1是map2的子集// 此时已满足窗口覆盖了twhile (findAll(map1, map2)) {if ((end - start + 1) < minLen) {minLen = end - start + 1;l = start;r = end;}// 左端点收缩的同时把其中的元素个数移除掉if (map2.containsKey(s.charAt(start))) {map2.put(s.charAt(start), map2.get(s.charAt(start)) - 1);}start++;}}return l == -1 && r == -1 ? "" : s.substring(l, r + 1);}// 判断map1是否是map2的子集public static boolean findAll( HashMap<Character, Integer> map1, HashMap<Character, Integer> map2) {Set<Map.Entry<Character, Integer>> set = map1.entrySet();for (Map.Entry<Character, Integer> entry : set) {if (entry.getValue() > map2.getOrDefault(entry.getKey(), 0)) return false;}return true;}}
收获：
将一个字符串的字符和对应个数初始化到一个map中
String s = "abcdssd";HashMap<Character, Integer> map = new HashMap<>();for (int i = 0; i < s.length(); i++) {map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);}
关于map的
getOrDefault()方法，获取指定key的value，如果key不存在则获取默认值，可以避免空指针异常
遍历一个HashMap的常用方法
HashMap map = new HashMap();Set<Map.Entry> set = map.entrySet();for (Map.Entry entry : set) {sout(entry);}
判断一个char-map是否是另一个char-map的子集
// map1 是否包含 map2public static boolean contains(HashMap<Character, Integer> map1, HashMap<Character, Integer> map2)Set<Map.Entry<Character, Integer>> set = map1.entrySet();for (Map.Entry<Character, Integer> entry : set) {if (map2.get(entry.getKey()) > entry.getValue()) return false;}return true;
