LeetCode刷题滑动窗口（串联所有单词的子串+最小覆盖的子串）Java

一串联所有单词的子串题目解析我们将s中的一整个字符串根据words中的每一个字符串的个数分为几个部分就拿例题一来解释我们将s中三个三个为一组最终也就是要找到words中的所有的异位词跟我上一个讲解的寻找所有的异位词的思想是一样的但是这个题目在那个的基础上是需要注意几个点的就是我们right移动的步长是words上每一个数组的长度然后我们也不能简单的就从头开始一个一个的分还需要从第二个字符开始分等等这个也是看你words中的长度的代码演示public static ListInteger findSubstring(String s, String[] words) { //s barfoothefoobarman, words [foo,bar] ListInteger retnew ArrayList(); MapString,Integerhash1new HashMap(); //先统计words中的每一个字符串的长度以及有几个字符串 int lenwords[0].length();//以例题中举例就是3 int wordsNum words.length;//以例题中举例就是2 //将words中的元素丢进hash1中 for (String s1:words){ hash1.put(s1,hash1.getOrDefault(s1,0)1);//现在就是foo1 bar1 } for (int i 0; i len; i) { MapString,Integerhash2new HashMap(); for (int left i,righti,count0; rightlen s.length(); rightlen) { //进窗口 String ins.substring(right,rightlen); hash2.put(in,hash2.getOrDefault(in,0)1); //依旧是hash表中可以有多个相同的元素可以出现foo2这样的情况但是count中始终是有效的才能加进去 if (hash2.get(in)hash1.getOrDefault(in,0)){ count; } //判断 if (right-left1len*wordsNum){ //出窗口维护count String outs.substring(left,leftlen); //这个时候我们的窗口已经大于应该有的数值了并且此时我们的out这个字符串还不符合我们的有效值的时候 if (hash2.get(out)hash1.getOrDefault(out,0)){ count--; } //上面说的就是这个情况我们需要出掉left的值 hash2.put(out,hash2.get(out)-1); leftlen; } //经过上面的判断以及维护以及出掉无效left的值之后还是满足有效值是我们需要的时候这个时候就是正确的下标了 if (countwordsNum){ ret.add(left); } } } return ret; }二最小覆盖的子串题目解析第一步还是将目标字符串通过遍历的形式加进一个哈希表1中并且定义一个count变量来记录有效的数值有效的字母的种类接下来依旧是进窗口维护count判断然后出窗口以及修改count最后就是在合适的地方更新结果这一套下来跟上面以及之前讲过的滑动窗口还是类似的当然这里都是字母我们依然可以使用数组来模拟哈希表让我们的时间更快代码演示class Solution { public static String minWindow(String s, String t) { char[]sss.toCharArray(); char[]ttt.toCharArray(); int[]hash1new int[128]; int kinds0; for (char ch:tt){ if (hash1[ch]0){ kinds; } hash1[ch]; } int[]hash2new int[128]; int minlenInteger.MAX_VALUE; int begin-1; for (int left 0,right0,count0; right ss.length; right) { //进窗口维护count char inss[right]; hash2[in]; if (hash2[in]hash1[in]){ count; } //判断 while (kindscount){ char outss[left]; //更新结果出窗口 if (right-left1minlen){ minlenright-left1; beginleft; } if (hash2[out]hash1[out]){ count--; } hash2[out]--; left; } } if (begin-1){ return new String(); }else { return s.substring(begin,beginminlen); } } }