【leetcodehot10076】最小覆盖子串

解法一：（滑动窗口）在 s 上滑动窗口，通过移动 r 指针不断扩张窗口。当窗口包含 t 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。 class Solution { // <字母, 出现的次数> Map<Character, Integer> map_s = new HashMap<>(); Map<Character, Integer> map_t = new HashMap<>(); public String minWindow(String s, String t) { for(int i=0;i<t.length();i++){ // map_t.getOrDefault(a,0)：若a在map_t内，则返回key=a的value，否则返回0（默认值）。 map_t.put(t.charAt(i), map_t.getOrDefault(t.charAt(i),0)+1); } int left=0, right=-1; // Integer.MAX_VALUE的使用 // left_len和right_len不能=0，后面return的判断left_len==right_len会忽略(s=a,t=a)的情况 int min_len=Integer.MAX_VALUE, left_len=-1, right_len=-1; while(right<s.length()){ right++; // 不能放在后面，return的s.substring回错误，计算不出(s=a,t=a)的情况 if(right<s.length() && map_t.containsKey(s.charAt(right))){ // 放入map_s中，计数 map_s.put(s.charAt(right), map_s.getOrDefault(s.charAt(right),0)+1); } while(check() && left<=right){ // 是while(left++直到最小值)不是if() if(min_len > (right-left+1)){ min_len = right-left+1; left_len = left; right_len = right+1; } if(map_t.containsKey(s.charAt(left))){ // 一定存在，默认值为0也可 map_s.put(s.charAt(left), map_s.getOrDefault(s.charAt(left),0)-1); } left++; } } return left_len==-1 ? "" : s.substring(left_len,right_len); } public boolean check(){ Iterator iter = map_t.entrySet().iterator(); while(iter.hasNext()){ Map.Entry entry = (Map.Entry) iter.next(); Character key = (Character) entry.getKey(); Integer value = (Integer) entry.getValue(); if(map_s.getOrDefault(key,0) < value){ return false; } } return true; } } 注意： 对于char类型，其对应的包装类是Character判断某一key值是否存在：map_s.containsKey()，而不是map_s.isContainsKey()map_t.getOrDefault(a,0)：若a在map_t内，则返回key=a的value，否则返回0（默认值）。迭代： Iterator iter = map_t.entrySet().iterator(); while(iter.hasNext()){ Map.Entry entry = (Map.Entry) iter.next(); Character key = (Character) entry.getKey(); Integer value = (Integer) entry.getValue(); }