企业官网建设流程全解析

题目描述：

思路一

两个指针left和right都指向第一个元素
然后right指针向右移动，知道找到第一个包含的（包含的可以用一个map统计）
然后左指针向左移动，看能不能缩小范围，当左指针移动到窗口的字母比T的字母个数还少的时候，再移动右指针。

建立Map字典：

Map<Character,Integer>dicT=newHashMap<>();for(inti=0;i<t.length();i++){intcount=dicT.getOrDefault(t.charAt(i),0);dicT.put(t.charAt(i),count+1);}

用一个数组保存结果：

// 长度 l rint[]ans={-1,0,0};

需要特别注意的是：Map的value是Integer对象，如果使用==比较对象的话，是比较的地址，这个时候要么用equals方法，或者用.intValue

if(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"";}Map<Character,Integer>dicT=newHashMap<>();for(inti=0;i<t.length();i++){intcount=dicT.getOrDefault(t.charAt(i),0);dicT.put(t.charAt(i),count+1);}//需要的数目intrequired=dicT.size();//已经构建的数目intformed=0;// 左右两个指针intl=0,r=0;// 窗口字母个数Map<Character,Integer>windowCounts=newHashMap<>();// 长度 l rint[]ans={-1,0,0};while(r<s.length()){charc=s.charAt(r);intcount=windowCounts.getOrDefault(c,0);windowCounts.put(c,count+1);if(dicT.containsKey(c)&&windowCounts.get(c).intValue()==dicT.get(c).intValue()){System.out.println(1);formed++;}while(l<=r&&formed==required){System.out.println("l"+l+"r"+r);c=s.charAt(l);if(ans[0]==-1||r-l+1<ans[0]){ans[0]=r-l+1;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"";}Map<Character,Integer>dicT=newHashMap<>();for(inti=0;i<t.length();i++){intcount=dicT.getOrDefault(t.charAt(i),0);dicT.put(t.charAt(i),count+1);}List<Pair<Integer,Character>>filterS=newArrayList<>();for(inti=0;i<s.length();i++){charc=s.charAt(i);if(dicT.containsKey(c)){filterS.add(newPair<>(i,c));}}intl=0,r=0,formed=0;intrequired=dicT.size();int[]ans={-1,0,0};Map<Character,Integer>window=newHashMap<>();while(r<filterS.size()){charc=filterS.get(r).getValue();intcount=window.getOrDefault(c,0);window.put(c,count+1);if(window.get(c).intValue()==dicT.get(c).intValue()){formed++;}while(l<=r&&formed==required){c=filterS.get(l).getValue();intstart=filterS.get(l).getKey();intend=filterS.get(r).getKey();if(ans[0]==-1||end-start+1<ans[0]){ans[0]=end-start+1;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和value
Array初始长度为0，之后每次按照之前的1.5倍来扩容，在这个例子上面效率比LinkedList高