优选算法的时序之窗：滑动窗口专题(二)

专栏算法的魔法世界​​​​​​个人主页手握风云目录一、例题讲解1.1. 最大连续1的个数 III1.2. 找到字符串中所有字母异位词1.3. 串联所有单词的子串1.4. 最小覆盖子串一、例题讲解1.1. 最大连续1的个数 III题目要求是二进制数组也就是数组中的元素只有0和1。最多翻转k个0而不是恰好也就是当数组中0的个数小于k就不用真的去翻转k个0。如果我们按照题目要求解题代码会非常不好写因为我们还要去翻转0。我们可以转化一下我们从数组当中找出一个最长子数组并且这个子数组中0的个数不超过k个这样我们就不用再去进行翻转0的操作。我们先来思考一下暴力枚举我们先固定数组当中的第一个元素为起点然后向后移动当子数组中0的个数超过k就停止如下图所示。我们还需要一个额外的变量zero来统计0的个数。接下来根据暴力枚举进行优化。先定义left和right指针指向数组的第一个元素然后让right指针向后移动。直到left与right所构成的子数组中0的个数大于k。根据暴力枚举的思路接下来就让left指针也向右一位right指针也要回退再向右移动。在这段区间内right还是依旧走到我们原来的位置。通过上面的分析我们发现right指针不需要回退让left指针直接越过这段区域。这时我们就会发现同向双指针也就是利用滑动窗口来解决。步骤还是“进窗口→判断→出窗口→更新结果”。进窗口当right遇到1的时候无视遇到0zero1。判断当zerok时left向右移动完成出窗口的操作。public class Solution { public int longestOnes(int[] nums, int k){ int ret 0; for (int left 0,right 0,zero 0;right nums.length; right){ if(nums[right] 0) zero;//进窗口 while(zero k){//判断 if(nums[left] 0) zero--;//出窗口 ret Math.max(ret,right-left1); } return ret; } }1.2. 找到字符串中所有字母异位词我们看下上面的示例1p可以重新排列为abc、acb、bac、bca、cab、cba。s中的索引则为[0,2]、[6,8]最终输出结果为[0,6]。首先我们需要思考如何判断两个字符串为异位词我们可以利用两个哈希表来统计字符串中字母出现的个数如果个数相等则两个字符串为异位词。我们先来思考暴力解法先把字符串p丢进hash1中然后从字符串s中找到长度与p相等的子串丢进hash2中并统计子串中出现的字母个数。其实我们从上图中很容易想到如何对暴力解法进行优化统计完第一个子串让里面的字符开始进出哈希表。就像窗口一样从头到尾并且滑动窗口的长度是固定的与p的长度相等。然后我们就可以利用滑动窗口的步骤来解题进窗口把字符丢进hash2中判断当窗口的长度大于p的长度时就要进行出窗口的操作最后检查两个哈希表中的字符数量是否一致更新结果。由于题目当中的字符串仅包含小写字母所以我们可以定义一个大小为26的数组来与哈希表判断是否相等还需要判断进出窗口这样时间复杂度就为26n→。但如果我们遇到更难的题目就可能会超时我们还需要对最后的更新做优化。我们再额外定义一个变量来统计“有效字符”的个数这个“有效字符”指的是p中的字符。进入后如果hash2中的有效字符小于hash1中的字符则count出去前我们需要检查出去的字符是否等于hash1中的字符则出去的是有效字符。进出窗口的同时维护count的大小。class Solution { public ListInteger findAnagrams(String s, String p) { ListInteger ret new ArrayListInteger(); char[] ss s.toCharArray(); char[] pp p.toCharArray(); int[] hash1 new int[26];//统计p中每一个字符出现的个数 for(char ch : pp) hash1[ch - a]; int[] hash2 new int[26];//统计窗口中字符出现的个数 for (int left 0,right 0,count 0;right s.length(); right){ char in ss[right]; if(hash2[in - a] hash1[in - a]) count;//进窗口与维护count if(right - left 1 p.length()){//判断 char out ss[left]; if(hash2[out - a]-- hash1[out - a]) count--;//出窗口与维护count } if(count p.length()) ret.add(left); } return ret; } }1.3. 串联所有单词的子串题目要求我们将字符串数组的子字符串串联然后在字符串s中的一个字串找出字母异位词。与上一题类似但这道题面对的是一个一个的字符串但我们依然可以利用滑动窗口和哈希表来解决。首先在哈希表上这里需要用到容器来映射字符串和字符串出现的次数在指针移动上right指针不能一次移动一个字符长度应与words里的字符串长度一致。对于滑动窗口的执行次数如下图我们只需要执行这3次滑动窗口的操作就可以找出其他操作都是多余的。所以滑动窗口的执行次数也是字符串数组中字符的长度。完整代码实现class Solution { public ListInteger findSubstring(String s, String[] words) { ListInteger ret new ArrayList(); MapString,Integer hash1 new HashMapString,Integer();//保存words里面单词的频次 for(String str : words) hash1.put(str, hash1.getOrDefault(str,0)1);//把单词丢进哈希表里面并单词个数 int len words[0].length(),m words.length; for (int i 0; i len; i) {//执行次数 MapString,Integer hash2 new HashMapString,Integer();//统计窗口内单词的频次 for (int left i,right i,count 0;right len s.length();right len){//count用来统计有效字符串的个数 //进窗口与维护count String in s.substring(right,rightlen); hash2.put(in,hash2.getOrDefault(in,0)1); if(hash2.get(in) hash1.getOrDefault(in,0)) count; //判断 if(right - left 1 len * m){ //出窗口与维护count String out s.substring(left,leftlen); if(hash2.get(out) hash1.getOrDefault(out,0)) count--; hash2.put(out,hash2.get(out) - 1); left len; } if(count m) ret.add(left); } } return ret; } }1.4. 最小覆盖子串我们先理清题目要求题目要我们从字符串s中找到一个最小子串与字符串t构成包含关系。如何没有这样的子串返回空字符串“”。我们还是先来思考一下暴力解法先定义两个指针我们以其中一个指针为起点另一个指针向右移动找到所有符合条件的子串从里面挑出最短的长度。如果转化成代码依然是借助哈希表 将遍历过的字符丢进哈希表中进行统计直到里面的字符个数大于等于t中的即可。接下来对暴力解法进行一个优化。我们看下图我们从s中找出一段符合要求的子串然后让left向后移动一步此时会出现两种情况要么缩小的区间还是符合要求要么不符合要求我们就让right向右移动并且在这期间right是不需要回退的。这时候我们就可以用滑动窗口与双指针来解决。进窗口把s中的字符串丢进哈希表中统计。当窗口是合法的时候判断两个哈希表里的字符个数再让left向左移动。我们最后是要返回一个字符串所以们需要知道起始位置和最终位置来决定我们什么时候出窗口。如果我们只去遍历一遍哈希表那么这个算法的时间复杂度是非常高的。我们还需要对算法进行优化。与前两题一样在定义变量count。只不过这次的count是统计字符的种类因为在找字母异位词时子串和字符串是一一对应的关系这里字符却是大于等于的关系。进窗口之后比较hash1(in) hash2(in)这里之所以不是大于等于是因为不会统计进重复的子串。出之前比较hash1(out) hash2(out)就能保证出之后窗口不是有效的。因为统计的是字符的种类所以count hash1的长度。class Solution { public String minWindow(String s, String t) { char[] ss s.toCharArray(); char[] tt t.toCharArray(); int[] hash1 new int[128];//统计字符串t中的频次 int kinds 0;//t中有多少种字符 for(char ch : tt) if(hash1[ch] 0) kinds; int[] hash2 new int[128]; int minlen Integer.MAX_VALUE, begin -1; for(int left 0,right 0,count 0;right ss.length; right){ char in ss[right]; if(hash2[in] hash1[in]) count;//进窗口与维护count while(kinds count){//判断 //更新结果 if(right - left 1 minlen){ begin left; minlen right - left 1; } char out ss[left]; if(hash2[out]-- hash1[out]) count--;//出窗口与维护count } } if(begin -1) return new String(); else return s.substring(begin,beginminlen); } }