在网站文字上做笔记/外链发布平台大全

76. 最小覆盖子串 - 力扣（LeetCode）

class Solution {/**也是滑动窗口，思路简单，但实现起来容易出错。一个tmap记录目标串t的各个字符出现的次数；一个smap记录原串的某个滑动窗口里字符出现次数。两个指针left，right都从0开始，用right遍历原串s，如果smap包含了所有tmap的kv，那么肯定就匹配上了，这个时候呢，就更新left，进行++操作，每加一次，就看是不是不满足smap包含了所有tmap的kv，如果不满足就停止left的++。*/public String minWindow(String s, String t) {if(s == null || t==null || s.length()==0 || t.length()==0){return "";}Map<Character,Integer> targetMap=new HashMap<>();// 这里其实也可以用charAtfor(char c:t.toCharArray()){targetMap.put(c,targetMap.getOrDefault(c,0)+1);}int left=0,right=0;// t字符串里不同字符的数量int tCnt=targetMap.size();int sCnt=0;//Integer.MAX_VALUEint start=0,minLen=1000005;Map<Character,Integer> sMap=new HashMap<>();while(right<s.length()){char c=s.charAt(right);sMap.put(c,sMap.getOrDefault(c,0)+1);if(targetMap.containsKey(c) && sMap.get(c).intValue()==targetMap.get(c).intValue()){sCnt++;}// right-left-1，因为下标left到right之间字符串的长度范围是right-left+1，减去1等于t.length，这个长度才是真实的临界值while(sCnt==tCnt && right-left-1>=t.length()){char sc=s.charAt(left);if(right-left+1<minLen){start=left;minLen=right-left+1;}sMap.put(sc,sMap.get(sc)-1);left++;if(targetMap.containsKey(sc) && sMap.get(sc).intValue()<targetMap.get(sc).intValue()){// 说明匹配的子串字符种类数不一样了，left就不能再++了sCnt--;}}right++;}return minLen==1000005?"":s.substring(start,start+minLen);}
}