系统学习算法： 专题二 滑动窗口

题目一：

算法原理：

依然第一反应是暴力枚举，将所有的子数组都枚举出来，找到满足条件的长度最小的子数组，但是需要两层循环，时间复杂度来到O（N^2）

接下来就该思考如何进行优化

如果此时的子数组已经满足条件，那么包括该子数组之后的子数组就没必要枚举了，因为长度一定大于这个子数组，不满足题目要求，所以这里我们可以进行优化

然后该数组也是具有单调性，这时你可能有疑问，这个数组不是无序的吗，怎么会有单调性呢

其实单调性不止有从小到大这种递增的单调性或者从大到小这种递减的单调性，还有正数求和的单调性，以及负数求差的单调性

比如这道题，里面的数都是正整数，所以对子数组求和，那么长度越长，和也就一定越大，这也是单调性

那么有单调性的话，我们要想到什么算法呢？当然有双指针和二分啦

其实双指针下面有许多分类，什么快慢双指针，异向双指针，同向双指针等等，其中同向双指针也叫做滑动窗口，即两个指针移动的方向是同向的，那么就比较像一个长度变化的窗口在向左或者向右滑动

而这道题就要用到滑动窗口，算法的通用步骤如下：

1.left=0，right=0，使得两个指针从同一起点出发

2.进窗口，即right往右移动，把窗口拉长

3.判断条件，看看此时是否要出窗口，即left往右移动，把窗口拉窄

4.更新条件（更新条件的位置不确定，要根据题目要求来确定更新的位置）

其中2到4之间是在循环里面的，直到right越界，即窗口被拉出边界了

用这道题来解释

第一步：我们要设置双指针left和right，同时定义一个变量为sum

第二步：在循环right<数组长度时，这时候sum加上right对应的值，然后right++

第三步：判断此时sum有没有达到题目要求

如果sum小了，说明还不需要出窗口，要继续拉长窗口

如果sum大了，说明此时需要出窗口，更新此时的长度，然后把窗口拉窄，让left--，sum同时减去left对应的值，继续循环判断条件，直到不需要出窗口，

最后当right超出数组下标时，退出循环

也是很简单的思路，大了我就减一点，小了我就加一点，最后找到长度最小的情况

只不过这种算法根据单调性，排除了许多没必要枚举的情况，在时间复杂度上只有O（N），即right遍历完数组，即可，空间复杂度也全是常量O（1），但是不要看等会代码有两层循环就认为时间复杂度是O（N^2），要结合实际操作来计算时间复杂度

代码1：

class Solution {public int minSubArrayLen(int target, int[] nums) {//设置变量int n = nums.length, sum = 0, len = Integer.MAX_VALUE;//开始循环for (int left = 0, right = 0; right < n; right++) {sum += nums[right]; // 进窗⼝（小了就加一点）while (sum >= target) // 判断{len = Math.min(len, right - left + 1); // 更新结果sum -= nums[left++]; // 出窗⼝（大了就减一点）}}return len == Integer.MAX_VALUE ? 0 : len;//如果不存在符合条件的就返回0}
}

题目二：

算法原理：

子串和子数组其实区别不大，都是连续的，只不过一个在字符串内，一个在数组内

依然是先暴力枚举，将所有子串的结果都枚举出来，用两层循环，第一层循环固定起始点，第二层循环固定终点，当出现重复的时候找到终点，退出第二层循环，然后等第一层循环结束，找到其中子串长度最大的值即可，同样时间复杂度是O（N^2）

那么如何判断是否重复呢，可以采用哈希表

也就是第一种方法：暴力+哈希

那么如何优化呢，我们可以在暴力枚举的过程中发现，如果找到第一个子串后，第二个子串的起点没必要又重新来遍历一次，因为第二个子串是第一个子串的子串

比如abcdc

第一次遍历从a开始，找到终点d，则第一个子串为abcd

第二次遍历从b开始，这时就没必要再遍历c，d了，因为bcd是abcd的子串，所以直接判断起点是否与c重复了，如果重复就继续跳过，直到跳过第一个c，这样就直接来到dc子串

那么使用滑动窗口的条件除了单调性，还有连续性，比如找子串就是连续性的，至于怎么想到用滑动窗口，那么就只能多积累经验了

依然用滑动窗口的通用步骤：

先设置left=0，right=0

进入循环，然后right对应的字符扔进哈希表中，right++（进窗口，将窗口拉长）

这时循环进行判断：如果此时是重复的，那么从哈希表中删除left对应的值，left++（出窗口，将窗口拉窄），直到跳过第一次出现重复字符的位置

然后更新此时的长度

最后返回长度即可

当然这道题我们也不一定真要创建一个哈希表，字符最大ASCII码也就到128，直接用数组下标也可以判断

代码1：

class Solution {public int lengthOfLongestSubstring(String s) {//将字符串拆成一个一个字符的数组char[] str=s.toCharArray();//用数组当作哈希表int[] hash=new int[128];//套用滑动窗口通用模板int left=0,right=0,n=s.length();int ret=0;while(right<n){//进窗口，str[right]也就是s第right个字符，将该字符的ASCII码值作为数组下标，给该下标的值加1//表示出现1次该字符hash[str[right]]++;//如果值大于1，说明该字符出现了2次while(hash[str[right]]>1){//出窗口，直到跳过第一次出现该重复字符的位置（将窗口拉窄）hash[str[left++]]--;}//此时的子串是不重复的，找到最长的子串长度ret=Math.max(ret,right-left+1);//将窗口拉长right++;}return ret;}
}

时间复杂度也是降为O（N），空间复杂度如果不使用真正哈希表，用代码这种模拟哈希表的话，空间复杂度会来到O（N），如果用真正的哈希表，只有O（1），所以哈希表这种数据结构是非常重要的

题目三：

算法原理：

如果真的按照题目要求，将0翻转成1，那么就会很麻烦，将数组不停翻来翻去，那么难度直接上升好几个维度

这时就要转变思维，怎么间接地转换题目要求

因为最多可以翻转k个0，其实也就是说一个子数组中，最多出现k个0

那么这时就不需要进行翻转了，只需要判断子数组中出现多少个0的问题了

而子数组这种连续性的问题，也就可以用滑动窗口算法

仍然也是套用公式（难点主要是间接转变题目的要求，代码都是相同的套路）

先设定两个指针以及一个变量作为长度计数器

然后循环

进窗口

循环判断条件是否出窗口

更新此时长度

代码1：

class Solution {public int longestOnes(int[] nums, int k) {//初始化int left=0,right=0,len=0;int count=0;//循环while(right<nums.length){//进窗口if(nums[right]==0){count++;}//判断条件while(count>k){//出窗口if(nums[left]==0){count--;}left++;}//更新结果len=Math.max(len,right-left+1);right++;}//返回结果return len;}
}

题目四：

算法原理：

根据题目的要求可知，有时候减左边，有时候减右边，完全无从下手

有时候看到题目觉得很难，其实就是题目将简单的方法隐藏起来了，用一种很难的方法来告诉你

这时就要用到正难则反，以后大部分题也都需要用到这个方法

设数组中全部的值的和为sum，左右要减去的总和为题目要求的x，那么中间剩下的连续的数组的和就为sum-x

这一下就回到了我们熟悉的连续性，而不是左减一下右减一下，那么就要想到滑动窗口，因为要求的是最小操作数，所以这时题目就换而言之为求数组中的子数组的和为sum-x的最长子数组

那么接下来就直接套用滑动窗口的模板即可

代码1：

class Solution {public int minOperations(int[] nums, int x) {//初始化int left=0,right=0,sum=0;int len=-1;//求数组的和for(int i=0;i<nums.length;i++){sum+=nums[i];}//用来计算此时子数组的和int s=0;//如果全部之和都没有x大，那么肯定就不可能存在符合题目要求的情况if(sum<x){return -1;}//滑动窗口的模板while(right<nums.length){//进窗口s+=nums[right];//判断条件while(s>sum-x){//出窗口s-=nums[left];left++;}//更新条件if(s==sum-x){len=Math.max(right-left+1,len);}right++;}return len==-1?-1:nums.length-len;}
}

有两点地方需要注意：

1.如果数组之和小于x，那么就说明x减去整个数组都大于0，则肯定不等于0，这时可以直接判断不存在，返回-1

2.len初始化不能为0，因为存在一种情况为整个数组的和刚好等于x，那么此时的len就为0，因为要找到和sum-x的子数组，而sum-x又为0，题目中也说数组的值最小为1，就不存在这样一个子数组，所以没有就为0，

则此时判断是否存在情况的时候，就会出现值为0的两种情况：

没有找到解，len没被修改过，要返回-1；

找到了解，但是len也为0，要返回num.length-len；

刚好是相反的情况，所以len初始化不能为0，即0不能作为判断是否存在的条件，要为-1或者其他负数

题目五：

算法原理：

这种情景题首先要理解题目意思，基本都是看题目大概了解是个什么意思，然后再结合示例明白具体是怎么个要求

读懂题意后，自己转化成简洁语言要求即可

这道题我转化就为：在一个数组中，找到一个最长的子数组，其中这个子数组最多只有两种不同的元素，并返回这个最长子数组的长度

然后把握题目特征（也就是找关键词，在脑海中思考大概用什么算法），子数组问题，连续性

大概就与滑动窗口相关了

仍然先用暴力枚举模拟一下操作过程，然后再进行优化

暴力枚举的话就是起点从下标为0开始往后枚举，直到出现第三种水果，终点停止

那么此时起点往后移动一位，然后继续按照上述操作重复，直到起点为数组的最后一位

那么其中优化的地方就有，如果起点往后移动一位跳过的元素，后面还有该元素，那么这个子数组里面仍然有三种不同的值，所以起点要一次性跳过所有的该元素才行，这是一个优化

然后终点没有必要又从起点开始遍历，因为之前已经遍历过，所以终点只需要保持在原位即可，等到起点跳过某一元素的所有元素，终点再继续往后走

那么如何判断子数组里面有多少种不同的值，只需要把数组下标扔进哈希表即可，用一个变量作为种类计数器进行判断即可

然后就是套用滑动窗口的模板

代码1（哈希表）：

class Solution {public int totalFruit(int[] f) {Map<Integer, Integer> hash = new HashMap<Integer, Integer>(); // 统计窗口的水果种类int ret = 0;for (int left = 0, right = 0; right < f.length; right++) {int in = f[right];hash.put(in, hash.getOrDefault(in, 0) + 1); // 进窗⼝while (hash.size() > 2) {int out = f[left];hash.put(out, hash.get(out) - 1); // 出窗⼝if (hash.get(out) == 0)hash.remove(out);left++;}// 更新结果ret = Math.max(ret, right - left + 1);}return ret;}
}

虽然哈希表的操作时间复杂度都是O（1）级别，但是因为使用到了容器，且操作很频繁的话，时间消耗其实还是挺多的，这时候我们就可以用数组模拟哈希表，因为底下说明了数组中最大的值一定小于数组的长度，所以直接用数组的长度作为模拟数组的长度即可

代码2（用数组模拟哈希表）：

class Solution {public int totalFruit(int[] fruits) {//初始化int left=0,right=0,count=0;int len=-1;//模拟数组int[] hash=new int[fruits.length];//滑动窗口模板while(right<fruits.length){//判断是否为新种类if(hash[fruits[right]]==0){count++;}//进窗口hash[fruits[right]]++;//判断条件是否出窗口while(count>2){//出窗口hash[fruits[left]]--;if(hash[fruits[left]]==0){count--;}left++;}//更新条件len=Math.max(len,right-left+1);right++;}return len;}
}

时间消耗上比用哈希表大大优化了，基本上是质的飞跃

题目六：

算法原理：

这道题大致分为两步，第一步是怎么判断异位词，第二步是怎么判断字符串中所有的异位词

首先解决第一步，最暴力的方式就是将两个字符串先按照字典序排序，然后再进行比较，这样肯定可以比较出来是否是异位词，但是效率不高

再多想一想的话，就可以想到通过比较两个字符串中，每次字符出现的次数是否相等，那么这样就不需要进行排序再比较了，直接通过字符数是否相等即可判断两个字符串是否是异位词，那么就可以采用哈希表，将字符与出现个数建立一一映射关系，采用两个哈希表，一个统计s，一个统计p

第二步的话，可以想到滑动窗口，滑动窗口大致分为两类：窗口大小不确定，和窗口大小固定，而这道题就是滑动窗口大小固定的题，因为窗口大小一定是等于p字符串的长度

那么接下来通过遍历，将s字符串用滑动窗口的步骤，判断是否是异位词即可，但是步骤中需要稍微修改，那就是之前窗口大小不确定的题中判断条件是不确定left要移动多少，所以用到是循环，但是窗口固定大小就可以确定right++，那么left也只用++一次即可，所以用if就好

还有一个优化，那就是每次判断异位词的，都是要将每种字符一个一个比较，效率不是很高，可以采用count变量作为统计当前窗口的有效字符，而如何判断进窗口后和出窗口后的字符是不是有效字符呢，只需要判断该字符在s哈希表出现的次数小于等于p哈希表的次数，说明该字符是有效的，count++，如果大于，那就说明这个字符是无效字符，出不出都无所谓，count不需要改变

最后判断count是否等于p的长度，如果等于，就说明全都是有效字符，那么肯定是异位词，将left的值加到顺序表中，反之则不是异位词

代码1（哈希表）：

class Solution {public List<Integer> findAnagrams(String s, String p) {//map用来统计p字符串中每个字符的数量，map1用来统计s遍历到的子串的字符数量HashMap<Character,Integer> map=new HashMap<>();HashMap<Character,Integer> map1=new HashMap<>();ArrayList<Integer> list=new ArrayList<>();//将p里面字符和出现数量建立一一映射的关系for(int i=0;i<p.length();i++){char ch=p.charAt(i);if(map.get(ch)==null){map.put(ch,1);}else{int val=map.get(ch);map.put(ch,val+1);}}//开始滑动窗口，count作为判断条件int count=0,left=0,right=0;while(right<s.length()){//进窗口，将元素放进map1char in=s.charAt(right);if(map1.get(in)==null){map1.put(in,1);}else{int val=map1.get(in);map1.put(in,val+1);}//滑动右边界right++;//如果此时的字符属于有效字符if(map1.get(in)<=map.getOrDefault(in,0)){count++;}//如果此时窗口的长度大于p字符串if(right-left>p.length()){//出窗口，将元素拿出来char out=s.charAt(left);//如果此时的字符属于有效字符if(map1.get(out)<=map.getOrDefault(out,0)){count--;}map1.put(out,map1.get(out)-1);//滑动左窗口left++;}//如果此时是异位词if(count==p.length()){list.add(left);}}return list;}
}

当然也可以用数组模拟哈希表

代码2（用数组模拟哈希表）：

class Solution
{public List<Integer> findAnagrams(String ss, String pp) {List<Integer> ret = new ArrayList<Integer>();//如果不习惯charAt，也可以先转化为字符数组，用下标来使用字符char[] s = ss.toCharArray();char[] p = pp.toCharArray();int[] hash1 = new int[26]; // 统计字符串 p 中每⼀个字符出现的个数for(char ch : p){hash1[ch - 'a']++;}int[] hash2 = new int[26]; // 统计窗⼝中每⼀个字符出现的个数int m = p.length;for(int left = 0, right = 0, count = 0; right < s.length; right++){char in = s[right];// 进窗⼝ + 维护 countif(++hash2[in - 'a'] <= hash1[in - 'a']) count++; if(right - left + 1 > m) // 判断{char out = s[left++];// 出窗⼝ + 维护 countif(hash2[out - 'a']-- <= hash1[out - 'a']){count--; }}// 更新结果if(count == m){ret.add(left);}}return ret;}
}

题目七：

算法原理：

和上面一道题很类似，上面那题判断异位词是字符，而这道是字符串，所以可以借鉴上面题目的解题步骤，但是也有几点不同，那就是滑动窗口的分割起点要多次循环，也就是要进行多次滑动窗口，因为对s如果从0开始，往后按照words字符串的长度len切割，有可能切不到，所以要从0开始切割，从1开始切割，……直到len-1开始切割

而且滑动窗口每次移动也不是一步一步移了，而是移动字符串的长度len，left和right也是同理

还有一个细节，那就是每次滑动窗口结束后，准备重新开始新的滑动窗口，要进行哈希表清零和count清零操作

具体就是代码实现，这道题也是算比较难的考验算法原理转化为代码形式的题

代码1：

class Solution {public List<Integer> findSubstring(String s, String[] words) {//map存words里面的映射关系，map1存滑动窗口中的映射关系HashMap<String,Integer> map=new HashMap<>();HashMap<String,Integer> map1=new HashMap<>();List<Integer> list=new ArrayList<>();//将words存进哈希表for(String str:words){if(map.get(str)==null){map.put(str,1);}else{int val=map.get(str);map.put(str,val+1);}}//len为words中一个字符串的长度，l为异位词的长度int left=0,right=0,count=0,len=words[0].length(),l=0;for(int i=0;i<words.length;i++){l+=len;}//最外层循环是滑动窗口的次数for(int cishu=0;cishu<len;cishu++){//确定left和right的起点right=cishu;left=cishu;//开始本次的滑动窗口while(right<s.length()&&left<=s.length()-l){//进窗口//String因为不可变性，+=拼接效率太低，可以采用StringBuffer进行拼接StringBuffer sb=new StringBuffer("");if(right+len<=s.length()){for(int i=right;i<right+len;i++){sb.append(s.charAt(i));}//因为哈希表泛型定义的String，所以要转回来String s1=sb.toString();map1.put(s1,map1.getOrDefault(s1,0)+1);//判断加进来的是否是有效字符串if(map1.get(s1)<=map.getOrDefault(s1,0)){count++;}//右窗口滑动right+=len;//判断滑动窗口有没有比异位词还长if(right-left>l){//出窗口//将之前字符串删除sb.delete(0,len);for(int i=left;i<left+len;i++){sb.append(s.charAt(i));}s1=sb.toString();//如果删之前发现该字符串是有效字符串if(map1.get(s1)<=map.getOrDefault(s1,0)){count--;}//删除map1.put(s1,map1.get(s1)-1);//左窗口滑动left+=len;}//如果此时滑动窗口中是异位词if(count==words.length){list.add(left);}            }else{//如果right后面的字符构不成一个len长度的字符串break;}}//进行清零，为下一次滑动窗口做准备count=0;map1.clear();}return list;}
}

里面用到了许多方法，以及优化上String的拼接改为StringBuffer（当然这里也可以使用substring方法），一次性写出来会比较困难，本人也是经过多次调试修改才写出来，确实很锻炼代码能力

题目八：

算法原理：

题目的意思也很简单，就是找到s字符串中涵盖t字符串所有字符的最小子串，还是先用暴力枚举的方法，大致理清操作步骤，定义left和right，left和right都从0开始，如果出现了t中的字符，对应计数器就++，然后right一直往右移动，直到最后一个字符，然后left往右移动一步，right又从left位置开始，继续往右移动，循环上面的步骤，直到left也到最后的字符位置

这是暴力枚举所有子串的情况的方法，里面依旧有许多优化的空间，比如right不需要又重新回到left的位置，只需要固定不动，等left自己移动即可，还有在判断是否符合涵盖子串的时候，按理来说是比较两个哈希表，但是根据上题提到的方法，可以用count来记录每个字符的种类个数，如果大于等于种类个数，就说明该子串是涵盖子串，这时候只需要比较是否是最小的子串，看看是否需要更改结果即可

大致与前几题类似，就不多赘述了

当然，一开始我们可以判断t的字符串长度是否大于s，因为如果大于了，那么s里面肯定就不可能涵盖t的所有字符的子串

代码1（哈希表）：

class Solution {public String minWindow(String s, String t) {//示例3的情况，直接返回空字符串if(t.length()>s.length()){return "";}//map1用来统计t的字符种类，map2用来统计s的字符种类及出现个数HashMap<Character,Integer> map1=new HashMap<>();HashMap<Character,Integer> map2=new HashMap<>();//将t建立起一一映射的关系for(int i=0;i<t.length();i++){if(map1.get(t.charAt(i))==null){map1.put(t.charAt(i),1);}else{int val=map1.get(t.charAt(i));map1.put(t.charAt(i),val+1);}}//count是有效字符种类，len是当前子串长度，cur是最小子串的起始位置，min是最小子串的长度int left=0,right=0,count=0,len=0,cur=0,min=0;//开始滑动窗口的步骤while(right<s.length()){//进窗口map2.put(s.charAt(right),map2.getOrDefault(s.charAt(right),0)+1);//如果进的是有效字符，字符种类加1if(map1.getOrDefault(s.charAt(right),0)>=map2.get(s.charAt(right))){count++;}//长度加1len++;//窗口右边界扩大right++;//判断条件（count的有效字符种类大于t的长度，即当前窗口内的字符串已经涵盖了t的所有字符）while(count>=t.length()){//更新条件，看看当前子串是否是最小子串（其中用min==0作为一开始的最小子串）if(len<min||min==0){//将最小子串的起始位置和长度进行更新cur=left;min=len;}//出窗口（先判断当前要出的是否是有效字符，且是否将该有效字符的所有个数全出完）if(map2.get(s.charAt(left))<=map1.getOrDefault(s.charAt(left),0)){count--;}//出窗口map2.put(s.charAt(left),map2.get(s.charAt(left))-1);//窗口左边界缩小left++;//长度减1len--;}}//返回最小字符的起始位置后的min长度的字符串return s.substring(cur,cur+min);}
}

 我们之前提到过虽然哈希表这个容器的时间复杂度为O（1），但是内存消耗还是很大的，所以如果能用数组模拟哈希表的话，就用数组模拟，这道题的题目提示中也有写s，t字符串都是由英文字符构成，所以直接创建长度为128的数组即可

代码2（用数组模拟哈希表）：

class Solution {public String minWindow(String ss, String tt) {//如果charAt用着不习惯，可以先转成数组，用下标来使用char[] s = ss.toCharArray();char[] t = tt.toCharArray();int[] hash1 = new int[128]; // 统计字符串 t 中每⼀个字符的频次int kinds = 0; // 统计有效字符有多少种for (char ch : t)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 < s.length; right++) {char in = s[right];if (++hash2[in] == hash1[in])count++; // 进窗⼝ + 维护 countwhile (count == kinds) // 判断条件{if (right - left + 1 < minlen) // 更新结果{minlen = right - left + 1;begin = left;}char out = s[left++];if (hash2[out]-- == hash1[out])count--; // 出窗⼝ + 维护 count}}if (begin == -1)return new String();elsereturn ss.substring(begin, begin + minlen);}
}