三亚旅游网站策划书,企业网站建设的定位,哈尔滨网站建设价格低,郴州网站设计公司76. 最小覆盖子串 - 力扣#xff08;LeetCode#xff09;
class Solution {/**也是滑动窗口#xff0c;思路简单#xff0c;但实现起来容易出错。一个tmap记录目标串t的各个字符出现的次数#xff1b;一个smap记录原串的某个滑动窗口里字符出现次数。两个指针left#x…76. 最小覆盖子串 - 力扣LeetCode
class Solution {/**也是滑动窗口思路简单但实现起来容易出错。一个tmap记录目标串t的各个字符出现的次数一个smap记录原串的某个滑动窗口里字符出现次数。两个指针leftright都从0开始用right遍历原串s如果smap包含了所有tmap的kv那么肯定就匹配上了这个时候呢就更新left进行操作每加一次就看是不是不满足smap包含了所有tmap的kv如果不满足就停止left的。*/public String minWindow(String s, String t) {if(s null || tnull || s.length()0 || t.length()0){return ;}MapCharacter,Integer targetMapnew HashMap();// 这里其实也可以用charAtfor(char c:t.toCharArray()){targetMap.put(c,targetMap.getOrDefault(c,0)1);}int left0,right0;// t字符串里不同字符的数量int tCnttargetMap.size();int sCnt0;//Integer.MAX_VALUEint start0,minLen1000005;MapCharacter,Integer sMapnew HashMap();while(rights.length()){char cs.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-left1减去1等于t.length这个长度才是真实的临界值while(sCnttCnt right-left-1t.length()){char scs.charAt(left);if(right-left1minLen){startleft;minLenright-left1;}sMap.put(sc,sMap.get(sc)-1);left;if(targetMap.containsKey(sc) sMap.get(sc).intValue()targetMap.get(sc).intValue()){// 说明匹配的子串字符种类数不一样了left就不能再了sCnt--;}}right;}return minLen1000005?:s.substring(start,startminLen);}
}
