012最小覆盖子串

最小覆盖子串题目链接https://leetcode.cn/problems/minimum-window-substring/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答public String minWindow(String s, String t) { int flagt.length(); StringBuilder sb new StringBuilder(); int length s.length(); int minInteger.MAX_VALUE; String ans; for(int l0, r0; llength; r){ if(flag0){ while(true){ if(t.indexOf(sb.charAt(0))!-1){ if(flag10){ break; } flag; } l; sb.deleteCharAt(0); } if(minsb.length()){ minsb.length(); anssb.toString(); } } if(rlength){ break; } else if(t.indexOf(s.charAt(r))!-1){ flag--; } sb.append(s.charAt(r)); } return ans; }分析我的解答不正确。我的解题思路为用一个变量flag维护当前窗口缺少t的字符个数但是在维护flag时我只是简单的根据当前字符是否存在于t中来进行判断flag是否作出改变但是当t中存在重复元素时这种维护方法是不可行的。看了官方题解后的解答//解法一采用两个哈希表存储字符及字符个数 //看了官方题解后的解答时间复杂度还是较高可以思考预处理字符串s进行优化 //预处理字符串s在遍历s是我们遍历了一些不需要的字符所以我们可以在遍历之前将s中无关紧要的字符提前删去从而进行优化。 //时间复杂度设字符集大小为 C则渐进时间复杂度为 O(C⋅∣s∣∣t∣) //空间复杂度设字符集大小为 C 则渐进空间复杂度为 O(C) MapCharacter,Integer tMap new HashMap(); MapCharacter,Integer sMap new HashMap(); public String minWindow(String s, String t) { int ansLenInteger.MAX_VALUE; int l0, r-1; int ansL-1, ansR-1; int sLens.length(); for(int i0; it.length(); i){ tMap.put(t.charAt(i),tMap.getOrDefault(t.charAt(i),0)1); } while(rsLen){ r; if(rsLen tMap.containsKey(s.charAt(r))){ sMap.put(s.charAt(r),sMap.getOrDefault(s.charAt(r),0)1); } while(lr check()){ if(r-l1ansLen){ ansLenr-l1; ansLl; ansRr; } if(tMap.containsKey(s.charAt(l))){ sMap.put(s.charAt(l),sMap.get(s.charAt(l))-1); } l; } } return ansL-1 ? : s.substring(ansL,ansR1); } public boolean check(){ Iterator iter tMap.entrySet().iterator(); while(iter.hasNext()){ Map.Entry entry (Map.Entry)iter.next(); Character key (Character)entry.getKey(); Integer value (Integer)entry.getValue(); if(sMap.getOrDefault(key,0)value){ return false; } } return true; } //解法二用一个数组存储滑动窗口中的字符个数再用一个变量debate统计当前窗口还缺乏的字符总数 //debate为0时缩小窗口的左边边界 //时间复杂度O(MN)M、N分别为字符串s、t的长度 //空间复杂度O(C)C为字符集的长度 public String minWindow(String s, String t) { int[] cnt new int[256]; int debatet.length();//欠缺的字符总数 int ansLenInteger.MAX_VALUE, ansL-1;//窗口大小 窗口的左边界 int l0, r0; int sLens.length(); for(int i0; it.length(); i){ cnt[t.charAt(i)]--; } while(rsLen){ if(cnt[s.charAt(r)]0){ debate--; } cnt[s.charAt(r)]; if(debate0){//无欠缺字符开始缩小窗口 while(lr cnt[s.charAt(l)]-10){ cnt[s.charAt(l)]--; l; } if(r-l1ansLen){ ansLenr-l1; ansLl; } } r; } return ansL-1 ? : s.substring(ansL,ansLansLen); }分析​ 1、本题均采用滑动窗口哈希表解决问题关键在于用什么方法维护字符个数在什么条件下比较并统计答案。​ 2、方法一采用两个哈希表来分别保存t的字符及字符个数、滑动窗口中属于t的字符及字符个数每次窗口发生变化后都需要将两个哈希表进行比较才能判断当前窗口是否符合题目条件而方法二采用一个数组来统计当前窗口每个字符欠缺的字符个数再通过一个变量debate记录当前窗口欠缺的字符总数debate可以根据数组大小的变化来维护我们可以直接根据debate是否为0来判断是否需要统计答案而无需遍历数组。总结本题主要采用滑动窗口哈希表解题既可以采用Map存储字符及字符个数也可以采用数组来存储。我们可以采用一个变量来记录缺乏的字符总数方便判断何时开始缩小窗口并比较和统计答案。