沈阳优化网站关键词,长沙找工作包吃住6000,2024年最新时政热点,河南省建设集团有限公司网站滑动窗口简介
滑动窗口就是利用单调性#xff0c;配合同向双指针来优化暴力枚举的一种算法。 该算法主要有四个步骤 1. 先进进窗口 2. 判断条件#xff0c;后续根据条件来判断是出窗口还是进窗口 3. 出窗口 4.更新结果#xff0c;更新结果这个步骤是不确定的#xff0c…滑动窗口简介
滑动窗口就是利用单调性配合同向双指针来优化暴力枚举的一种算法。 该算法主要有四个步骤 1. 先进进窗口 2. 判断条件后续根据条件来判断是出窗口还是进窗口 3. 出窗口 4.更新结果更新结果这个步骤是不确定的应题目要求判断是在进窗口前更新结果还是出窗口前更新结果。 1. 长度最小的子数组
题目链接209. 长度最小的子数组 - 力扣LeetCode 题目细节信息
1.数组中都是正数 2.在数组中找到长度最小的子数组且子数组中的元素和小于target值
解法滑动窗口 我们先定义一个left指针和right指针left和right之间就是一个窗口。在定义一个变量sum来记录[left,right]区间的和。 根据题目要求我们先确定第一个sum大于等于target值得右边界所以我们先让right不断进窗口。 以题目中的实例1为例 接着我们根据sum的值来判断是否进窗口还是出窗口。sum的值无非会遇到两种情况。 当sum小于等于target的时候我们先要更新最小长度和sum的值接着在进窗口即让left 如下图 之前left指向的元素已经不在窗口里面了这也是理解出窗口的一个图解。 当sum小于target时我们进窗口进行了即right 滑动窗口的正确性 为什么能判断滑动窗口是对的呢 因为数组中的数据都是正数当right找到第一个边界使sum大于等于target的值时我们就没必要让right继续向后走了因为数组中都是正数right继续走下去sum会变大但是len也会变长此时len肯定就不是我们要的结果了。所以不让right向后走就避免了其他不符合题意情况的枚举了。 代码实现
代码一我写的形式 public int minSubArrayLen(int target, int[] nums) {int nnums.length;int left0,right0;int retInteger.MAX_VALUE;int sumnums[right];while(rightn){if(sumtarget){right;//进窗口if(rightn){sumnums[right];}}else{retMath.min(ret,right-left1);//更新长度最小值sum-nums[left];//更新sum值left;//出窗口}}return retInteger.MAX_VALUE?0:ret;}
代码二 public int minSubArrayLen(int target, int[] nums) {int nnums.length;int lenInteger.MAX_VALUE;int sum0;for(int left0,right0;rightn;right){//进窗口sumnums[right];while(sumtarget){//这里要用while循环lenMath.min(len,right-left1);//更新最小长度sum-nums[left];//更新sum的值left;//出窗口}}return lenInteger.MAX_VALUE?0:len;}
2.无重复字符的最长字串
题目链接3. 无重复字符的最长子串 - 力扣LeetCode 题目解析在字符串中找到一个连续且无重复字符的子字符串并返回其长度。
解法一暴力枚举(会超时)
枚举从字符串的第一个字符开始往后无重复字符的子串可以到什么位置找出一个最大长度的即可。
因此我们可以通过一个哈希表来记录往后枚举的过程中字符是否出现重复的情况。
//时间复杂度O(n^2)
//空间复杂度O(1)
import java.util.*;
class Solution {public int lengthOfLongestSubstring(String s) {int len s.length();int ret 0;for(int i 0; i len; i) {int[] hash new int[128];for(int j i; j len; j) {hash[s.charAt(j)];if(hash[s.charAt(j)] 1) {break;}ret Math.max(ret, j - i 1);}}return ret;}
}
解法二滑动窗口
此时我们可以通过滑动窗口来优化上面的暴力枚举。
首先先通过一种枚举的情况来分析如下图 当我们枚举时当right遇到第一个重复的字符a时我们就不必要让right继续往后走了因为前面的left的位置没变当right继续往后走left和right之间是一定有重复的字符的。
所以此时我们可以让right先固定在原地先让left指针往后走直到left指针跳过重复的字符right才能继续完后走。
但是当left往后走的时候right没必要往回退到和left一样的位置因为当left没有跳过第一个重复的字符时right撑死只能走到第二个a的位置且left往后走了此时子串的长度肯定是比left没有往后走时短的。
两个指针没有回退这时就可以使用滑动窗口了。 这里先解释下上面的hash数组的意思 这里hash数组的下标为字符串中字符的ASCII值hash数组中的数据是该字符的出现次数。 滑动川口的解题步骤
1.进窗口让字符进入hash表中
2.判断和出窗口判断该字符是否重复出现如果重复出现则出窗口即将该字符从hash表中删除。
3.更新结果这里是先进行判断后才执行更新的操作。
代码实现
时间复杂度O(n)
空间复杂度O(n)public int lengthOfLongestSubstring(String ss) {int nss.length();char[] sss.toCharArray();int[] hashnew int[128];int left0,right0,ret0;while(rightn){hash[s[right]];//进窗口while(hash[s[right]]1){//判断字符是否重复出现hash[s[left]]--;//出窗口}retMath.max(ret,right-left1);//更新结果right;}return ret; }
3. 最大连续1的个数
题目链接1004. 最大连续1的个数 III - 力扣LeetCode 题目解析最多可以将数组中的k个0翻转为1返回数组经过翻转后数组中连续1的最大个数。 虽然题目中是要求我们翻转0但是如果我们遇到0就将其翻转为1的话接着进行新的枚举的时候就又要将翻转过的0重新翻转为0此时代码就会很难写且很复杂。 其实我们可以转换为求区间的长度只要该区间的0的个数没有大于k个就行了。 解法一暴力枚举zero计数器
定义一个left和right指针我们可以让left为起点向后枚举定义一个zero变量来保存枚举过程中遇到0的个数 如果zero的值大于k此时我们就可以让right指针停在该位置了因为此时right如果继续走下去left和right区间就是不符合题目要求了。
也就是说此时以left为起点的枚举得到的连续1的长度就是一个最优解了此时就可以更新结果
所以我们要换一个起点进行枚举既让left接着让right回到left的位置以新的left为起点继续right继续向后枚举重复上面的步骤。
解法二滑动窗口
再暴力枚举上进一步优化当我们让left的时候没必要将right重新指向left的位置因为当zero的值大于k时right撑死也时只能走到刚才停止的位置只有我们left跳过一个0的时候让zero减一让zero的值小于k时此时right才可以继续完后枚举。
此时发现left和right指针是同向运行且不会退我们就可以使用滑动窗口算法来解决该问题。 步骤一进窗口 当right完后枚举时遇到1就忽略如果遇到0就让zero的值加1 步骤二判断出窗口 当zero的值大于k时我们就出窗口也就时让left如果left遇到1就忽略如果遇到0就 让zero的值减1 步骤三更新结果 此时更新结果的步骤是在判断的步骤之后。 代码实现
//时间复杂度O(n)
//空间复杂度O(1) public int longestOnes(int[] nums, int k) {int left0,right0,zero0;int nnums.length;int ret0;while(rightn){if(nums[right]1){right;}else{right;zero;//出窗口}while(zerok){//判断if(nums[left]0){zero--;//进窗口}left;}retMath.max(ret,right-left);//更新结果}return ret;} 注意这里更新结果为什么不是right-left1呢因为我是再right之后再更新长度而不是再right之前更新长度。 更简练版本 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 - left 1); // 更新结果}return ret;}
这个版本就是再right之前更新长度所以更新长度时是right-left1 4.将x减到0的最小操作数
题目链接1658. 将 x 减到 0 的最小操作数 - 力扣LeetCode 题目解析
1.我们每次进行一次删减操作时我们都要将数组最左边或最右边的元素删去供下一次删减操作时使用
2.数组里面的都是正数 在该题中只有数组里面全是正数我们才能使用滑动窗口解决 分析因为当数组里面有负数或者为0的数据时当right到达第一个停止的位置时当我们的tmp减去一个负数或者数据为0的数时由于负数或0的缘故会导致[leftright]区间的和有可能是等于或大于tmp的所以此时进行新的枚举时right有可能会向前退也有可能继续向后退。 解题思路转换解决该题的时候我们有时候会删去最左边的元素有时候会删去最右边的元素但是这种情况太复杂了我们要转换思路。
正难则反
题目要求我们找到数组两边使x值减为0的最小个数我们就可以转换为求中间和为sum-x的最长子串。
解法一暴力枚举
套两层for循环遍历每一个子数组的情况根据子数组的和是否等于target的值我们就更新结果接着break跳出一层循环。
解法二滑动窗口
我们通过滑动窗口来优化枚举我们每进行一次新的遍历的时候我们发现没必要每次都让right回到left的位置因为数组里面都是正数当left之后[leftright]区间的和肯定是小于target的。
此时发现left和right指针都不回退此时就可以使用滑动窗口。 1.进窗口tmpnums[right] 2.判断出窗口判断tmp的值是否大于target如果大于出窗口即nums-nums[left] 3.更新结果当tmp的值等于target的时候我们就可以更新结果。 //时间复杂度O(n)
//空间复杂度O(1)public int minOperations(int[] nums, int x) {int sum0;for(int i0;inums.length;i){sumnums[i];}int ret-1;int targetsum-x;//处理细节if(target0) return -1;for(int left0,right0,tmp0;rightnums.length;right){tmpnums[right];//进窗口while(tmptarget){//判断tmp-nums[left];//出窗口}if(tmptarget){retMath.max(ret,right-left1);//更新结果}}if(ret-1) return -1;//此时没有找到子数组和为target的子数组else return nums.length-ret;} 5.水果成篮从这里开始比较认真
题目连接904. 水果成篮 - 力扣LeetCode 题目分析有一个fruit数组在数组中不同元素的值代表不同的水果种类相同元素的值代表水果的种类相同我们有两个篮子每个篮子只能装一种水果一个篮子中装的水果数量没有限制。如果摘水果的过程中一旦遇到与篮子中水果种类不同的水果树就停止采摘求这两个篮子能装的最大水果数量。
以上可以总结为一句话找一个连续的最长子数组该子数组中的水果种类不超出两种。
解法一暴力枚举哈希表
我们可以将每一个子数组的情况枚举出来枚举的过程中我们可以借助一个hash表来保存枚举过程中采摘水果的种类和数量。
我们用left为外层循环的标志right为内层循环的标志
枚举的小细节
1. 为了防止在[1,2,1]的情况下right指针会造成数组越界所以我们每次进行一次内循环时要对right指针进行判断是否越界。
2.当篮子中水果的种类也超出两种时也应该跳出该内层循环
3.在每一次采摘水果之前必须判断水果种类为2种时下次采摘的水果是否为第三种水果如果成立则跳出内部循环
4.每次进行一次新的外部枚举时我们也要将hash表中上次枚举保存水果的情况删掉。
代码
//空间复杂度:O(n)
//时间复杂度:O(n^2)public int totalFruit(int[] f) {MapInteger, Integer hash new HashMapInteger, Integer();int ret 0;for (int left 0; left f.length; left) {for (int right left; right f.length; right) {if (right f.length || hash.size() 2) {//判断数组是否越界和水果种类的数量break;}int in f[right];if (hash.size() 2 !hash.containsKey(in)) {//摘水果之前的判断break;}hash.put(in, hash.getOrDefault(in, 0) 1);ret Math.max(ret, right - left 1);}hash.clear();//在下次枚举之前删除此次枚举的情况}return ret;} 解法二滑动窗口
当我们进行新的left的枚举时我们没必要让right重新回到left的位置因为当left进行新的枚举时left往后走如果right重新返回到left指针的位置往后枚举的时候right会出现两种情况第一种情况right会停在在上一次left枚举时right的最后枚举的位置或者超过right最后枚举的位置。也就是说以新的left为新的起点进行right的枚举时right是一定会经过之前的枚举停下的位置的所以我们就不必要将right返回到left的位置。
通过上面的分析发现left和right指针是同向双指针这时我们就可以使用滑动窗口来解决这个问题。 解题步骤 1.定义left0right0 2.进窗口让hash[f[right]] 3.判断出窗口一个循环 当hash.size2时让hash[f[left]]--同时让left 4.更新长度 用哈希表来实现:
//时间复杂度O(n)
//空间复杂度O(n)public int totalFruit(int[] f) {MapInteger,Integer hashnew HashMapInteger,Integer();int ret0;for(int left0,right0;rightf.length;right){int inf[right];hash.put(in,hash.getOrDefault(in,0)1);//进窗口while(hash.size()2){//判断int outf[left];hash.put(out,hash.get(out)-1);//出窗口if(hash.get(out)0){hash.remove(out);}left;}retMath.max(ret,right-left1);//更新长度}return ret;}
用数组来实现 public int totalFruit(int[] f) {int nf.length;int[] hashnew int[n1];int ret0;for(int left0,right0,kind0;rightn;right){int inf[right];if(hash[in]0){kind;}hash[in];//进窗口while(kind2){//判断int outf[left];hash[out]--;//出窗口if(hash[out]0){kind--;}left;}retMath.max(ret,right-left1);//更新长度}return ret;} 6.找出字符串中所有的异位字符串
题目链接438. 找到字符串中所有字母异位词 - 力扣LeetCode 题目解析再s字符串中找出p字符串中的所有异位字符串 异位字符串就是相同字符但是字符的顺序不一样组成的字符串如abc、acb、bac、bca、cab和cba都是abc的异位字符串。 解决思路滑动窗口哈希表 如何判断两个字符串互为异位字符串呢 第一种方法我们可以将两个字符串按字典的顺序进行排序接着判断这两个字符串是否相同就行如果相同那么就是异位字符串如果不同则不是异位字符串。 第二种方法借用两个哈希表hash1来存储p字符串hash2来存储s字符串最终判断两个哈希表是否相同如果相同那么互为异位字符串如果不同则不是异位字符串。 以下图为例 我们在s中找p的异位字符串我们使用暴力枚举时第一次枚举时 当right-left1长度为p.length()时第一次枚举就结束了如下图 此时第一次枚举就结束了进行第二次枚举让left同时让right返回到left的所处的位置 进行第二次枚举时right继续走向right-left1p.length()的位置此时发现right依然会进过之前的字符b和字符a 所以每一次进行新的枚举没必要让right回到left的位置这样left和right都是同向双指针这时我们就可以用滑动窗口来解决问题。 进窗口当right-left1s.length时hash2[in] 判断出窗口 如果right-left1p.length()就出窗口让hash2[out]--同时让left 更新结果 要判断是异位字符串在更新结果 代码实现
//时间复杂度O(nm)
//空间复杂度O(nm)public ListInteger findAnagrams(String ss, String pp) {ListInteger retnew ArrayList();char[] sss.toCharArray();char[] ppp.toCharArray();int[] hash1new int[26];int[] hash2new int[26];for(char ch:p){hash1[ch-a];}for(int left0,right0;rights.length;right){char ins[right];hash2[in-a];//进窗口if(right-left1p.length){//判断char outs[left];hash2[out-a]--;//出窗口left;}//更新结果if(right-left1p.length){//判断是否互为异位字符串boolean flagtrue;for(int i0;i26;i){if(hash1[i]!hash2[i]){flagfalse;}}if(flagtrue) ret.add(left);//更新结果}}return ret;}
进一步优化此时我们可以在更新结果那里优化一下因为在更新结果那里我们需要遍历两个哈希表时间复杂度还是太大了我们可以通过一个变量count统计窗口中的有效字符个数。
下图解释了什么是有效字符一次类推 前面我们用hash1统计了字符串p中的情况用hash2统计了字符串s中的情况。
进窗口之后我们对hash1[in]和hash2[in]进行比较如果hash2[in]小于等于hash1[in]那么此时就可以认为该字符是一个有效字符让count
出窗口之前我们对hash1[out]和hash2[out]进行比较如果hash2[out]小于等于hash[out],此时就可以认为出去的字符是一个有效字符让count--
最终在更新结果的时候我们只要判断count是否等于p.length如果等于p.length就更新结果如果不等于p.length就不更新结果。
代码实现 public ListInteger findAnagrams(String ss, String pp) {ListInteger retnew ArrayList();char[] sss.toCharArray();char[] ppp.toCharArray();int[] hash1new int[26];int[] hash2new int[26];for(char ch:p){hash1[ch-a];}for(int left0,right0,count0;rights.length;right){char ins[right];hash2[in-a];//进窗口if(hash2[in-a]hash1[in-a]) count;//更新有效字符个数if(right-left1p.length){//判断char outs[left];if(hash2[out-a]hash1[out-a]) count--;//更新有效字符个数hash2[out-a]--;//出窗口left;}//更新结果if(countp.length) ret.add(left);}return ret;}
7.串联所有单词的子串
题目链接30. 串联所有单词的子串 - 力扣LeetCode 我们如果将words的每一个字符串看成一个整体在以这个整体为单位去在s中找串联所有单词的子串这时就跟找异位字符串差不多了。如下图 这道题的思路和第6题的解题思路差不多这里讲不同点假设words数组字符串的长度为m数组的长度为len 1.right和left指针的位移 right和left一次位移的长度为m 2.hash表的不同 这里的哈希表存的是字符串的种类和数量即HashString,Integer 3.进行滑动窗口的次数 次数为m次 这里对不同点3进行解释 代码实现 public ListInteger findSubstring(String s, String[] words) {MapString,Integer hash1new HashMapString,Integer();//存储wordsListInteger retnew ArrayListInteger();for(String str:words){hash1.put(str,hash1.getOrDefault(str,0)1);}int lenwords[0].length(), mwords.length;for(int i0;ilen;i){//执行滑动窗口MapString,Integer hash2new HashMapString,Integer();//存储sfor(int lefti,righti,count0;rightlens.length();rightlen){String ins.substring(right,rightlen);hash2.put(in,hash2.getOrDefault(in,0)1);if(hash2.get(in)hash1.getOrDefault(in,0)) count;//判断出窗口while(right-left1m*len){String outs.substring(left,leftlen);if(hash2.get(out)hash1.getOrDefault(out,0)) count--;hash2.put(out,hash2.getOrDefault(out,0)-1);leftlen;}//更新结果if(countm) ret.add(left);}}return ret;}
8.最小覆盖子串
题目链接76. 最小覆盖子串 - 力扣LeetCode 题目分析我们需要再字符串s中找一个子串在这个子串中的字符种类需要包含字符串t中所有字符类型如果t中有了重复的字符那么从s中找的子串的该字符的数量必须大于等于t中的重复字符的数量。
比如t为aba那么在s中找的子串中字符a的数量是不能小于t中a的字符数量。
解题思路
首先我们还是想到暴力枚举hash表我们将字符串中s的字符都枚举一遍在枚举的过程中如果遇到符合题目要求的子串此时就更新结果接着立刻换一个字符进行新的枚举以此类推下去。
优化思路滑动窗口
如下图 此时我们需要让left往后移动一步当left之后left和right之间就会出现两种情况。
第一种情况
如果left之后left和right之间的字符种类没有发生变化当我们让right回到left的位置进行新的枚举时right还是会回到原来的位置。如下图 第二种情况
如果left之后left和right之间的字符种类发生变化当我们让right回到left的位置时进行新的枚举为了找到新的符合题目要求的子串此时right肯定时跑到原来位置的后面。如下图 所以我们发现没必要每次都要将right返回到原来left的位置我们只要根据每次left移动后的情况根据情况来让right不动或者往后移动。
此时发现left和right都是同向双指针此时就可以使用滑动窗口。
在使用滑动窗口前我们要用到两个哈希表一个用来存储s字符串的情况另一个用来存储t字符串的情况。 进窗口hash2[in] 判断更新结果出窗口 判断在s中找的子串是否符合题目要求也就是hash2与hash1对应字符的数量是否一 样 跟新结果由于我们这里找到一个符合题目要求的子串就要跟新结果所以此处的跟新结果实在出窗口之前 出窗口hash2[out]-- 在进一步优化更新结果
在更新结果那里我们需要遍历两个哈希表来判断找的子串是否符合题目要求每个哈希表都要遍历一遍时间复杂度还是太大了此时我们可以通过count变量来统计hash1和hash2中完全相同的字符数量。 这里的完全相同是指数量和种类都相同。 在进窗口之后如果hash2[in]hash1[in],那么我们认为在in在hash1和hash2中是完全相同的字符则让count
出窗口之前如果如果hash2[in]hash1[in],那么我们认为在in在hash1和hash2中是完全相同的字符则让count--
此时判断条件就变为counthash1.size().
代码实现 public String minWindow(String ss, String tt) {char[] sss.toCharArray();char[] ttt.toCharArray();int[] hash1new int[128];//存储tint[] hash2new int[128];//存储s;int kinds0;//记录t中有效字符的种类for(char ch:t){if(hash1[ch]0) kinds;hash1[ch];}int minlenInteger.MAX_VALUE, begin-1;for(int left0,right0,count0;rights.length;right){//进窗口char ins[right];hash2[in];if(hash2[in]hash1[in]) count;//判断更新出窗口while(kindscount){//更新结果if(right-left1minlen){minlenright-left1;beginleft;}//出窗口char outs[left];if(hash2[out]hash1[out]) count--;hash2[out]--;//出窗口left;//维护窗口}}if(begin-1) return new String();else return ss.substring(begin,beginminlen);}
