leetcode.76 最小覆盖子串Java

题目描述思路一两个指针left和right都指向第一个元素然后right指针向右移动知道找到第一个包含的包含的可以用一个map统计然后左指针向左移动看能不能缩小范围当左指针移动到窗口的字母比T的字母个数还少的时候再移动右指针。建立Map字典MapCharacter,IntegerdicTnewHashMap();for(inti0;it.length();i){intcountdicT.getOrDefault(t.charAt(i),0);dicT.put(t.charAt(i),count1);}用一个数组保存结果// 长度 l rint[]ans{-1,0,0};需要特别注意的是Map的value是Integer对象如果使用比较对象的话是比较的地址这个时候要么用equals方法或者用.intValueif(dicT.containsKey(c)Objects.equals(windowCounts.get(c),dicT.get(c))){formed;}或者if(dicT.containsKey(c)windowCounts.get(c).intValue()dicT.get(c).intValue()){formed;}如果直接对象相等是错的。完整代码packageSolution;importjava.util.HashMap;importjava.util.Map;/** * Author : fanc:最小覆盖子串 * Date : 2019-08-26 20:16 */publicclassSolution76{publicstaticStringminWindow(String s,String t){if(s.length()0||t.length()0){return;}MapCharacter,IntegerdicTnewHashMap();for(inti0;it.length();i){intcountdicT.getOrDefault(t.charAt(i),0);dicT.put(t.charAt(i),count1);}//需要的数目intrequireddicT.size();//已经构建的数目intformed0;// 左右两个指针intl0,r0;// 窗口字母个数MapCharacter,IntegerwindowCountsnewHashMap();// 长度 l rint[]ans{-1,0,0};while(rs.length()){charcs.charAt(r);intcountwindowCounts.getOrDefault(c,0);windowCounts.put(c,count1);if(dicT.containsKey(c)windowCounts.get(c).intValue()dicT.get(c).intValue()){System.out.println(1);formed;}while(lrformedrequired){System.out.println(llrr);cs.charAt(l);if(ans[0]-1||r-l1ans[0]){ans[0]r-l1;ans[1]l;ans[2]r;}//尝试左指针向右移动l;windowCounts.put(c,windowCounts.get(c)-1);if(dicT.containsKey(c)windowCounts.get(c).intValue()dicT.get(c).intValue()){formed--;}}r;}returnans[0]-1?:s.substring(ans[1],ans[2]1);}}优化方法优化的滑动窗口我们只需要考虑S包含T的元素因此可以把S包含T的元素单独列出来做一个filter然后遍历这个filter。/** * Author : fanc * Date : 2019-09-01 13:56 */publicclassSolution76_2{publicStringminWindow(String s,String t){if(t.length()0||s.length()0){return;}MapCharacter,IntegerdicTnewHashMap();for(inti0;it.length();i){intcountdicT.getOrDefault(t.charAt(i),0);dicT.put(t.charAt(i),count1);}ListPairInteger,CharacterfilterSnewArrayList();for(inti0;is.length();i){charcs.charAt(i);if(dicT.containsKey(c)){filterS.add(newPair(i,c));}}intl0,r0,formed0;intrequireddicT.size();int[]ans{-1,0,0};MapCharacter,IntegerwindownewHashMap();while(rfilterS.size()){charcfilterS.get(r).getValue();intcountwindow.getOrDefault(c,0);window.put(c,count1);if(window.get(c).intValue()dicT.get(c).intValue()){formed;}while(lrformedrequired){cfilterS.get(l).getValue();intstartfilterS.get(l).getKey();intendfilterS.get(r).getKey();if(ans[0]-1||end-start1ans[0]){ans[0]end-start1;ans[1]start;ans[2]end;}l;window.put(c,window.get(c)-1);if(window.get(c).intValue()dicT.get(c).intValue()){formed--;}}r;}returnans[0]-1?:s.substring(ans[1],ans[2]1);}}在Java里面使用Pair来构建一个存放key和value的list可以使用getKey和getValue的方法来获取Pair里面的key和valueArray初始长度为0之后每次按照之前的1.5倍来扩容在这个例子上面效率比LinkedList高