企业官网建设流程全解析

一，串联所有单词的子串

题目解析：

我们将s中的一整个字符串根据words中的每一个字符串的个数分为几个部分，就拿例题一来解释，我们将s中三个三个为一组，最终也就是要找到words中的所有的异位词，跟我上一个讲解的寻找所有的异位词的思想是一样的，但是这个题目在那个的基础上是需要注意几个点的，就是我们right移动的步长是words上每一个数组的长度，然后我们也不能简单的就从头开始一个一个的分，还需要从第二个字符开始分，等等，这个也是看你words中的长度的

代码演示：

public static List<Integer> findSubstring(String s, String[] words) { //s = "barfoothefoobarman", words = ["foo","bar"] List<Integer> ret=new ArrayList<>(); Map<String,Integer>hash1=new HashMap<>(); //先统计words中的每一个字符串的长度以及有几个字符串 int len=words[0].length();//以例题中举例就是3 int wordsNum= words.length;//以例题中举例就是2 //将words中的元素丢进hash1中 for (String s1:words){ hash1.put(s1,hash1.getOrDefault(s1,0)+1);//现在就是foo，1 bar，1 } for (int i = 0; i < len; i++) { Map<String,Integer>hash2=new HashMap<>(); for (int left = i,right=i,count=0; right+len <=s.length(); right+=len) { //进窗口 String in=s.substring(right,right+len); hash2.put(in,hash2.getOrDefault(in,0)+1); //依旧是hash表中可以有多个相同的元素，可以出现foo，2这样的情况，但是count中始终是有效的才能加进去 if (hash2.get(in)<=hash1.getOrDefault(in,0)){ count++; } //判断 if (right-left+1>len*wordsNum){ //出窗口+维护count String out=s.substring(left,left+len); //这个时候我们的窗口已经大于应该有的数值了，并且此时我们的out这个字符串还不符合我们的有效值的时候 if (hash2.get(out)<=hash1.getOrDefault(out,0)){ count--; } //上面说的就是这个情况，我们需要出掉left的值 hash2.put(out,hash2.get(out)-1); left+=len; } //经过上面的判断以及维护以及出掉无效left的值之后，还是满足有效值是我们需要的时候，这个时候就是正确的下标了 if (count==wordsNum){ ret.add(left); } } } return ret; }

二，最小覆盖的子串

题目解析：

第一步还是将目标字符串通过遍历的形式加进一个哈希表1中，并且定义一个count变量来记录有效的数值（有效的字母的种类），接下来依旧是进窗口，维护count，判断，然后出窗口以及修改count，最后就是在合适的地方更新结果，这一套下来跟上面以及之前讲过的滑动窗口还是类似的，当然，这里都是字母，我们依然可以使用数组来模拟哈希表，让我们的时间更快

代码演示：

class Solution { public static String minWindow(String s, String t) { char[]ss=s.toCharArray(); char[]tt=t.toCharArray(); int[]hash1=new int[128]; int kinds=0; for (char ch:tt){ if (hash1[ch]==0){ kinds++; } hash1[ch]++; } int[]hash2=new int[128]; int minlen=Integer.MAX_VALUE; int begin=-1; for (int left = 0,right=0,count=0; right <ss.length; right++) { //进窗口+维护count char in=ss[right]; hash2[in]++; if (hash2[in]==hash1[in]){ count++; } //判断 while (kinds==count){ char out=ss[left]; //更新结果+出窗口 if (right-left+1<minlen){ minlen=right-left+1; begin=left; } if (hash2[out]==hash1[out]){ count--; } hash2[out]--; left++; } } if (begin==-1){ return new String(); }else { return s.substring(begin,begin+minlen); } } }