优选算法《滑动窗口》

在优选算法的第一章当中我们了解了双指针算法，相信通过那几道算法题的讲解你已经知道该如何灵活的使用双指针了吧，那么接下来我们就接着来学习下一个优选算法——滑动窗口，你这时可能会疑惑这个算法在之前怎么完全没有听说过，没有关系接下来在本篇当中就将带你一步步的了解滑动窗口的算法原理以及在什么情况下适合使用滑动窗口来解决问题，并且还会通过几道算法题的讲解让你进一步的理解滑动窗口。那么接下来就开始本篇的学习吧！！！

1.滑动窗口算法

在此滑动窗口算法其实就是一种双指针中的特殊情况，只不过是因为在这种情况下的双指针有特殊的规律，因此我们就单独的将这种双指针的情况单独命名为一种算法，那么滑动窗口算法是什么情况下的双指针算法呢？接下来我们就来了解看看

在使用双指针当中，若出现两个指针从开始到结束一直都是朝着同一个方向移动的，并且都不会出现超另一个方向移动的情况这种就叫做滑动窗口，在此叫做这种算法是因为两个指针一直朝着同一个方向移动就像一个大小可能会变化的窗口一样。


 

那么了解了滑动窗口是什么之后，你可能会有疑惑了那滑动窗口该怎么用并且滑动窗口为什么算法逻辑是正确的呢，接下来我们就通过一道算法题来解决你的疑惑

209. 长度最小的子数组 - 力扣（LeetCode）

通过以上的题目描述就可以看出以上算法题要我们实现的是从给定的数组当中找到和大于给定值target的最大子数组，在此要注意的是题目要求的是子数组这就使得我们选取的数组元素必须是数组当中一段连续的区间；中间不能有中断的。

例如以上的示例1我们就不能像以下这样选取数组元素

 

了解了题目的要求之后接下来我们就来看看该如何来解决这道算法题

首先在没有思路之前我们先能想到使用暴力枚举来解决，在此就是先创建一个指针left来遍历原数组，之后再创建一个指针right每次从遍历时left的下标位置开始向后移动，并且再创建一个变量统计left到right这段区间内的元素值之和，每次统计之后再判断sum是否大于等于target，是的话就停止这一个left位置的子区间统计；并且记入这时子数组的长度，将left向后移动一位进行下一次的统计。最后当left移动到超出数组的范围之后就结束了所有满足条件的子数组的统计，最后将满条件的长度最小的子数组长度返回即可。通过以上算法实现在最坏的情况下要遍历数组两遍，因此暴力枚举的时间复杂度就为O(N^2),这种效率在这道题的数据范围下是会超时的

那么我们就要想该如何依据暴力枚举的算法来优化

通过以上使用暴力枚举时的流程图就可以看出其实在过程当中有很多的步骤是在做无用功的

当right移动到的位置l之后left到right区间之间的数组元素和正好大于给定的值target时在暴力枚举当中我们是在将left向后移动一位时再将right也移动到left的位置再进行新一轮的统计。但其实在这个这个过程就没有必要将right回退到left，这是因为在之前left到right的区间内的数组之和才恰好大于t或者等于target，这时我们将left右移一位之后区间内的和一定是小于或者等于或者大于target的，那么就说明不需要再将right回退到left的位置，这时就直接判断此时left到right之间的所有元素之和即可；这样就避免了很多的重复计算。

那么以上的算法优化就简单来说就是每次移动right指针之前都判断当前left到right区间内的元素之和是否大于或者等于targe若不是就将right++，否则就将left--，并且每次满足条件的区间都统计长度，这时我们就会发现在这个过程当中left都是一直朝着一个方向移动，属于同向双指针，这就符合我们说的滑动窗口的条件。

并且通过以上的分析也就证明了滑动窗口算法的合理性

并且我们还知道了为什么滑动窗口算法时间复杂度更低
▪ 窗⼝寻找的是：以当前窗⼝最左侧元素（记为 left ）为基准，符合条件的情况。也就是在这道题中，从 left 开始，满⾜区间和 sum >= target 时的最右侧（记为right ）能到哪⾥。
▪ 我们既然已经找到从 left 开始的最优的区间，那么就可以⼤胆舍去 left 。但是如果继续像⽅法⼀⼀样，重新开始统计第⼆个元素（ left ）往后的和，势必会有⼤量重复的计算（因为我们在求第⼀段区间的时候，已经算出很多元素的和了，这些和是可以在计算
下次区间和的时候⽤上的）。
▪ 此时， rigth1 的作⽤就体现出来了，我们只需将 left1 这个值从 sum 中剔除。从
right1 这个元素开始，往后找满⾜ left2 元素的区间（此时 right1 也有可能是满
⾜的，因为 left1 可能很⼩。 sum 剔除掉 left1 之后，依旧满⾜⼤于等于
target ）。这样我们就能省掉⼤量重复的计算。
▪ 这样我们不仅能解决问题，⽽且效率也会大大提升。

那么滑动窗口算法在使用时就分为以下的几个步骤

 

注意：在不同的算法题下更新是在不同的步骤之后的，在本题就是判断满足大于或者等于target的条件之后进行更新 

 

完成了该算法题的算法分析之后接下来我们就来实现代码

  1. class Solution {
  2. public:
  3.     int minSubArrayLen(int target, vector<int>& nums) 
  4.     {
  5.         //定义len为满足条件的子数组的最小值，一开始定义为int范围内的最大值
  6.         //sum为left到right区间内的元素值之和
  7.         int n=nums.size(),len=INT_MAX,sum=0;
  8.         for(int left=0,right=0;right
  9.         {
  10.             //当不满足条件时就进窗口
  11.             sum+=nums[right];
  12.             //判断当前区间是否条件
  13.             while(sum>=target)
  14.             {
  15.                 //更新最小子数组的长度，如果当前满足条件的区间长度比len小就更新
  16.                 len=min(right-left+1,len);
  17.                 //出窗口
  18.                 sum-=nums[left++];
  19.             }
  20.         }
  21.         //最后返回len时先判断len是否为INT_MAX；
  22.         //是就说明数组所有元素值之和都无法大于或者等于target此时就返回0
  23.         return len==INT_MAX?0:len;
  24.         
  25.     }
  26. };

2.滑动窗口相关算法题 

在以上我们了解滑动窗口算法是什么之后接下来就通过算法题来巩固该算法的使用，在此每道算法题还是会分为题目解析；算法原理讲解；代码实现三步来带着你一起吃透每道算法题，相信通过这些算法题的练习你会对滑动窗口算法有更深的理解

 2.1 无重复字符的最长子串

3. 无重复字符的最长子串 - 力扣（LeetCode）

题目解析 

通过以上的题目描述就可以看出该算法题要我们实现的是从给定的数组当中找出不含重复字符的最长子串，在此要注意的是子串和之前我们看到的子数组一样都必须是原给定数组或者字符串一段连续的区间

算法原理讲解

在看到这道算法题时我们一般是先想到使用暴力枚举的方式来解决，那就是创建两个指针变量left和right；使用left来遍历数组之后使用right来从每个left指针位置开始寻找满足条件的子字符，在此过程中每次子字符串满足条件时就更新最长子串长度len。最后就可以得到满足条件的最长的子串

以上示例1当中使用暴力枚举的过程图就如下所示：

在此在使用暴力枚举在最坏的情况下要遍历原数组两遍给，那么时间复杂度就为O(N^2)，在这道题给定的数据范围可能会超时

 

这时我们就要想如何基于暴力枚举下进行算法的优化将暴力枚举内的重复计算给消除。在暴力枚举当中就可以看出当固定left之后从后找满足条件的区间，这时在暴力枚举当中是在right移动之后出现子串中出现重复字符就将left++，并且将right移动到left的位置。但其实这个将right回退的过程是完全没必要的，因为将left向后移动一位之后当前到原来right的区间满足条件的子串不可能比原来的子串还长，所以这时就不要将right回退了，毕竟回退了之后还会移动到当前的位置就没必要做这些无用功了。

所以优化之后的算法简单来说就是当left到right之间的子串满足条件时就先更新子串的长度，之后直到子串出现重复字符就将left++;此时right不要动，之后进行完left的移动之后再进行判断不满足就继续移动left，直到left到right的区间内的子串满足条件就继续移动right

此时该优化之后的算法left和right为同向双指针，就属于滑动窗口算法，流程图如下所示：


 

在此就需要使用一个数组来模拟哈希表，这样就能判断当前left到right的区间内是否无重复字符 

注：在此s 由英文字母、数字、符号和空格组成，所以我们开一个大小为128的数组就完全足够了

 

代码实现

  1. class Solution {
  2. public:
  3.     int lengthOfLongestSubstring(string s) 
  4.     {
  5.         //创建数组hash来模拟哈希表，一开始将表内的数据都初始化为0
  6.         int hash[128]={0};
  7.         //创建变量len来统计满足条件的最长字串长度
  8.         int n=s.size(),len=0;
  9.         for(int left=0,right=0;right
  10.         {
  11.             //进窗口，将对应的哈希表内的值个数加一
  12.             char in=s[right];
  13.             hash[in]++;
  14.             //判断当前hash表下标in位置是否值大于1
  15.             while(hash[in]>1)
  16.             {
  17.                 //进行出窗口操作，将hash表内下标out位置的值减一
  18.                 char out=s[left];
  19.                 hash[out]--;
  20.                 //将left右移一位
  21.                 left++;
  22.             }
  23.             //更新最大子串len的长度
  24.             len=max(len,right-left+1);
  25.  
  26.         }
  27.         return len;
  28.         
  29.     }
  30. };

以上使用滑动窗口算法实现的代码虽然是两次循环的嵌套，但实际上就遍历一次原字符串s，时间复杂度为O(N) 

 

2.2 最大连续 1 的个数 III

1004. 最大连续1的个数 III - 力扣（LeetCode）

题目解析 

通过以上的题目描述就可以看出该算法题要我们实现的是将给定的数组内的最多k个0翻转，最终使得数组内得到的子数组元素全部为1，返回该子数组的长度

在此如果在解决这道算法题时如果每次翻转数组当中的0是真的将数组当中的元素改变，那么这道算法题就会变得十分的繁琐，因为我们在改变相应数组数组当中的0元素时我们不能确保此时的子数组是符合要求中长度最长的子数组，所以在进行下一次查找时原数组的内容已经被修改了，这就会使得接下来的操作都是错误的，因此使用这种方式就需要在一开始再创建一个和原数组一样的数组来保存原数组内的数据。但是这种方式不仅空间复杂度高操作过程还复杂，那么这时就要思考了能不能把题目的问题转化一下呢？

其实在该算法题当中不要去想怎么翻转，不要把问题想的很复杂，这道题的结果无非就是⼀段连续的 1 中间塞了 k个 0 嘛。因此，我们可以把问题转化成：求数组中⼀段最长的连续区间，要求这段区间内 0 的个数不超过 k 个。

因此要求最长的一段连续区间就可以使用滑动窗口来解决了

 

算法原理讲解

在该算法题中要求最长的一段连续区间使用滑动窗口来解决就需要一开始定义两个指针left和right一开始都指向数组的首元素，之后当数组内的0元素个数没有超过k时就进行进窗口操作也就是继续将left右移一位，如果出现了数组内的0元素个数超过k就进行出窗口操作也就是将left右移一位，直到数组内的0元素个数步超过k就更新最长子数组的长度，最后当left移动到数组的末尾时就完成了整个的操作

算法的流程图如下所示：


在此我们创建一个变量count来统计left到right区间内的元素0的个数

 

代码实现 

  1. class Solution 
  2. {
  3. public:
  4.     int longestOnes(vector<int>& nums, int k) 
  5.     {
  6.         //变量count统计窗口内值为0的元素个数，len为满足条件最长的子数组长度
  7.         int n=nums.size(),count=0,len=0;
  8.         for(int left=0,right=0;right
  9.         {
  10.             //进窗口，若right指向的数组下标位置的元素值为0，count就++
  11.             if(nums[right]==0)count++;
  12.             //判断count是否大于k
  13.             while(count>k)
  14.             {
  15.                 //出窗口，若left指向的数组下标位置的元素值为0，count就--
  16.                 if(nums[left++]==0)count--;
  17.             }
  18.             //更新最长子数组的长度
  19.             len=max(right-left+1,len);
  20.  
  21.         }
  22.         return len;
  23.     }
  24. };

 

2.3 将 x 减到 0 的最小操作数

1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

题目解析 

通过以上的题目描述就可以看出该算法题要我们求的是在给定的数组当中找出从原数组的两边找到能让x减去这些元素值恰好为零时这些元素的最小个数，如果无法实现x恰好减到0就返回-1

算法原理讲解

在此如果我们是完全按照题目给定的步骤来思考，这道算法题就会很复杂了，复杂的点就在于我们不知道在选取边界的元素时选取得顺序是什么，因为最终最小得元素个数情况下可能全部被选取到的元素都在原数组的左边也可能是全部在原数组的右边，当然也可能既有选取左边的也有右边的。这时我们就会发现如果从被选取元素正着考虑就很难解决了，那么这时我们就应该试着从要解决的事物反面考虑了

在此在这道题当中我们要从原数组两边当中选取出能使得x减到0的最小元素个数，其实不就是和求数组当中除被选取的元素之外数组内剩下的元素个数最多情况；这时数组当中除被选取的元素为最多且个数就为原数组的长度减去未被选择的元素个数。在此如果无法实现x恰好减到0这时未被选取到的元素个数就等于数组的长度。

这里我们就创建一个变量sum存储数组当中所有元素值减去给定值x的结果

所以综上分析就可以得出该算法题被我们转化为求数组当中和为sum的子数组当中最长的子数组长度，如果找不到一个子数组内的元素值为sum就返回-1

代码实现

  1. class Solution {
  2. public:
  3.     int minOperations(vector<int>& nums, int x) 
  4.     {
  5.         //s变量统计数组内所有元素值得和，len为最终窗口和内元素值为sum的最小值
  6.         int sum = 0, s = 0, len = -1, n = nums.size();
  7.         //遍历原数组统计数组元素之和
  8.         for (auto i : nums)
  9.             s += i;
  10.         //sum变量为s变量减去x变量的差
  11.         sum = s - x;
  12.         //处理特殊情况当sum小于0时就说明数组内不可能实现元素之和为x
  13.         if (sum < 0)
  14.             return -1;
  15.         //进行滑动窗口操作，count统计窗口内的所有元素值之和
  16.         for (int count = 0, left = 0, right = 0; right < n; right++) 
  17.         {
  18.             //进窗口，将right指向的下标位置的数组元素加到count变量内
  19.             count += nums[right];
  20.             //判断当前窗口内的和是否大于sum
  21.             while (count > sum) 
  22.             {
  23.                 //出窗口，将left指向的下标位置的数组元素值从count中减去
  24.                 count -= nums[left++];
  25.             }
  26.             //更新len变量的值
  27.             if (count == sum)
  28.                 len = max(right - left + 1, len);
  29.         }
  30.         //返回时判断是否有窗口和为sum
  31.         return len == -1 ? -1 : n - len;
  32.     }
  33. };

在以上代码中我们仅仅遍历一次原数组就实现题目要求，代码的时间复杂度为O(N) 

2.4 水果成篮 

904. 水果成篮 - 力扣（LeetCode）

题目解析

在这道看完题目你可能会比较疑惑，但其实这道题简单来说就是题目给定了一个数组，数组当中的每个元素就代表一个水果，并且同类型的水果使用同一个数来表示，例如示例1当中数组元素为[1,2,1]那么数组当中其实就有两种类型的水果分别是1和2。

在此给了我们两个篮子来装水果，要求每个篮子内的水果类型要相同，而且在采摘水果过程中必须要连续采摘不能跳跃之后采摘，就例如在示例2当中我们不能采摘完1之后跳过1去采摘2

 

算法原理讲解 

在这道算法题当中其实要求的就是取在数组当中取出一段子数组，要求子数组当中元素的类型不超过两种，这时返回这段子数组的长度。

那么这时这时我们使用暴力枚举就是从数组第一个元素开始遍历对应位置之后找出满足条件的子数组，最终返回最长的子数组长度。但根据之前的经验就可以知道这种情况下暴力枚举是有很多重复计算，在此根据单调性其实就可以将原来的暴力枚举优化为滑动窗口，只要窗口内整型类型小于等于2就进行进窗口的操作，直到窗口内的类型大于2就进行出窗口的操作，最后在出窗口之后更新最长的子数组长度

在该算法题当中使用滑动窗口算法的流程图如下所示：

在此在这道题当中我们要记录窗口内的元素类型以及对应元素的个数在此就需要用到哈希表；可以选择使用数组来模拟哈希表也可以直接使用容器unordered_map

使用数组来模拟哈希，以下kind为窗口内的元素种类数，len为满足条件的最长的子数组 

 

使用STL内的unordered_map就不需要创建变量kind来统计hash表内的元素个数，直接通过调用size()即可实现 

代码实现

用数组模拟哈希表版： 

  1. class Solution {
  2. public:
  3.     int totalFruit(vector<int>& fruits) 
  4.     {
  5.         const int N=1e5+5;
  6.         //使用数组模拟哈希表
  7.         int hash[N]={0};
  8.         //len为满足条件最长的子数组长度
  9.         int n=fruits.size(),len=-1;
  10.         for(int left=0,right=0,kind=0;right
  11.         {
  12.             //进窗口，当在哈希表内in下标位置在插入之前值为0就说明有新的元素插入哈希表就将kind++
  13.             int in=fruits[right];
  14.             if(hash[in]++==0)kind++;
  15.             //判断当前窗口内的元素种类是否大于2
  16.             while(kind>2)
  17.             {
  18.                 //出窗口，当在哈希表内out下标位置在删除之后值为0就说明有一个类型元素从哈希表内删除，这时就将kind--
  19.                 int out=fruits[left];
  20.                 if((--hash[out])==0)kind--;
  21.                 left++;
  22.             }
  23.            //更新len
  24.             len=max(len,right-left+1);
  25.         }
  26.      return len;   
  27.     }
  28. };

 

使用容器版：

  1. class Solution {
  2. public:
  3.     int totalFruit(vector<int>& fruits) 
  4.     {
  5.         //创建unordered_map对象来存储相应的元素以及对应的个数
  6.         unordered_map<int,int> hash;
  7.         int n=fruits.size(),len=-1;
  8.         for(int left=0,right=0;right
  9.         {
  10.             //进窗口
  11.             int in=fruits[right];
  12.             hash[in]++;
  13.             while(hash.size()>2)
  14.             {
  15.                 //出窗口
  16.                 int out=fruits[left];
  17.                 hash[out]--;
  18.                 //当hash对象内out元素内的second为0时
  19.                 //就说明现在窗口内已经没有该元素就调用erase实现删除操作
  20.                 if(hash[out]==0)hash.erase(out);
  21.                 left++;
  22.             }
  23.             len=max(len,right-left+1);
  24.  
  25.         }
  26.         return len;
  27.         
  28.     }
  29. };

 

2.5 找到字符串中所有字母异位词

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

题目解析 

通过以上的题目描述就可以看出该算法题要我们实现的是要在字符串s当中找到p字符串的所有的异或词的起始索引在此也就是要返回所有字串的首元素的地址。那么要了解的是什么是字符串的异或词，其实字符串的异或词就是只要是由字符串当中的元素组合出的字符串。例如以下示例

在示例1当中字符串abc的异或词就是使用a、b、c三个元素组合出的字符串。满足要求的就为abc、acb、bac、bca、cab、cba。

算法原理讲解

在这道题当中如果我们使用暴力枚举来从字符串s当中找出字符串p的所有异或词就需要一开始创建指针变量left一开始指向字符串s当中的首元素，创建一个哈希表1来存储字符串p内的元素；再创建一个哈希表2来存储left之后的三个元素。之后使用left遍历字符串s直到倒数第三个元素，每次遍历时都将left之后的三个元素存放到哈希表当中，比较此时的哈希表1和哈希表2是否内的元素是否相等，是的话就说明这三个字符是字符串p的异或词。接下来将left++之后将哈希表内的元素值重新赋值为0，再重复以上的操作直到left移动到字符串s的末尾。这时就可以将所有异或词的首元素坐标找出。

在以上暴力枚举算法当中我们需要遍历一次字符串s并且每次遍历到了left之后要将left位置开始的三个字符存放到哈希表当中，这样算法的效率是很低的，那么接下来我们就要想着该如何来优化暴力解法

 在此由于暴力解法当中的特性我们就可以试着将暴力解法优化为滑动窗口，在此就需要再创建一个变量right来表示窗口的右边界，当哈希表2内的元素种类和和个数大于哈希表1的时就将进行出窗口操作，直到当哈希表2内的元素种类和和个数和哈希表内相等就进行更新对应的索引位置

使用滑动窗口算法的流程图如下所示：

在以上当中len表示的是字符串p的长度，len2表示的left到right窗口的长度，count1表示的字符串p当中的元素种类数，count2表示的是left到right窗口内的字符种类数。

在以上我们使用这种方法来实现时就需要在更新时在对哈希表1和哈希表2内的进行遍历比较，只有两个表内的元素完全相同才能说明此时窗口内的字符串示字符串p的异或词，在len1==len2并且count1==count2还要进行判断是因为可能会出现窗口内的总的字符个数相同并且字符类型相同但是各个元素不一定完全相同，就例如aab和abb这种情况 

在以上我们的算法已经能解决该算法题，但我们在进行更新时还是要对哈希表hash进行遍历，虽然在该题中s 和 p 仅包含小写字母这就使得只需要进行26次的比较，效率还不会很低下。但是这时你可能就会好奇是否有更好的解法呢？

其实是有的，在这我们就不再去统计窗口内的元素个数而是需要统计窗口内的有效元素个数，那么有效元素个数是什么呢？

有效元素就是窗口内的元素可对应到字符串p内的元素，在此就创建一个变量sum来存储有效元素的个数，因此在进行进窗口操作之前就需要判断hash2[s[right-'a']]是否小于等于hash1[s[right-'a']],是的话就说明这时的元素为有效元素就将sum++，在出窗口之前判断hash2[s[left]-'a']是否小于等于hash1[s[left]-'a']，是的话就说明出此时窗口的元素是有效元素就需要将sum--

那么在出窗口操作时就只需要判断当前窗口的长度len是否大于字符串p的长度，是的话就只需要进行一次出窗口操作，出窗口之后如果len==sum再进行更新将这时的left下标插入到ret当中

例如以下示例：

通过以上的流程图就可以看出在字符串abcabcbb当中关于字符串abca的异或词索引只有0

代码实现

优化前面代码

  1. class Solution {
  2. public:
  3.     vector<int> findAnagrams(string s, string p) 
  4.     {
  5.         vector<int> v;
  6.         int len1=p.size(),count1=0;
  7.         int m[26]={0}, mp[26]={0};
  8.         for(auto& x:p)
  9.         {
  10.             if(m[x-'a']==0)
  11.             count1++;
  12.  
  13.             m[x-'a']++;
  14.             
  15.         }
  16.         int left=0,n=s.size(),len2=0,count2=0;
  17.         for(int right=0;right
  18.         {
  19.             //进窗口
  20.             if(mp[s[right]-'a']==0)
  21.             count2++;
  22.             mp[s[right]-'a']++;
  23.             len2=right-left+1;
  24.             while(len2>len1)
  25.             {
  26.                 //出窗口
  27.                 mp[s[left]-'a']--;
  28.                 
  29.                 if(mp[s[left]-'a']==0)
  30.                 count2--;
  31.  
  32.                 left++;
  33.                 len2=right-left+1;
  34.             }
  35.             //更新
  36.             if(count2==count1 && len1==len2)
  37.             {
  38.                 int flag=1;
  39.                 
  40.                 for(int i=0;i<24;i++)
  41.                 {
  42.                     if(m[i]!=mp[i])
  43.                     flag=-1;                 
  44.                 }
  45.                 if(flag==1)
  46.                 v.push_back(left);
  47.             }
  48.  
  49.         }
  50.         return v;
  51.         
  52.     }
  53. };


 

统计窗口内的有效字符个数，优化之后的代码

  1. class Solution {
  2. public:
  3.     vector<int> findAnagrams(string s, string p) 
  4.     {
  5.         //创建存储满足条件的异或词的字符串索引
  6.         vector<int> ret;
  7.         //hash1存储字符串p内的元素，hash2存储字符串s内的元素
  8.         int hash1[26]={0},hash2[26]={0};
  9.         //len表示字符串p的长度
  10.         int len=p.size();
  11.         //将p的的元素存储到hash1内
  12.         for(auto& x:p) 
  13.         {
  14.             hash1[x-'a']++;
  15.         }
  16.         int n=s.size();
  17.         //进行滑动窗口操作，sum统计窗口内的有效字符数
  18.         for(int left=0,right=0,sum=0;right
  19.         {           
  20.             int in=s[right]-'a';
  21.             //进窗口
  22.             hash2[in]++;
  23.             //在进窗口之后判断当前字符是否为有效字符，是就sum++
  24.             if(hash2[in]<=hash1[in])
  25.             sum++;
  26.             //当窗口的长度大于len时就进行出窗口操作
  27.             if(right-left+1>len)
  28.             {
  29.                 //在出窗口之前判断当前出去的字符是否为有效字符，是的话就将sum--
  30.                 int out=s[left]-'a';
  31.                 if(hash2[out]<=hash1[out])
  32.                 sum--;
  33.                 //出窗口
  34.                 hash2[out]--;
  35.                 left++;
  36.             }
  37.             //判断当前的子串是否为p的异或词，是的话就更新起始位置的索引到ret当中
  38.             if(sum==len)
  39.             {
  40.                 ret.push_back(left);
  41.  
  42.             }
  43.         }
  44.         return ret;
  45.         
  46.     }
  47. };

 

 

2.6 串联所有单词的子串 

30. 串联所有单词的子串 - 力扣（LeetCode）

题目解析

通过以上的题目描述就可以看出该算法题要我们实现的是从给定的字符串当中找出长度为words字符串数组当中的所有字符串组成的子串，那么在此也就是要在字符串s当中找到字符数组words所有的字符串异或词的字串

算法原理讲解

在这道算法题其实和以上我们解决的找到字符串当中所有的字母异或词那道算法题十分的相识，在此不同点就是在之前的算法题当中我们要找的是满足条件的字母的异或词的字符串，而在这道算法题当中需要找到满足条件的字符串异或词的字符串，在之前的每个元素是一个字符，而在这道题当中每个元素是一个字符串。

那么有了解决之前那道算法题的经验就就可以在这道算法题当中也使用滑动窗口来解决，只不过在此每次进窗口和出窗口时进和出的元素就不单是一个字符而是长度和words[i].length一样的字符串。那么在使用滑动窗口的具体过程就是一开始创建两个指向字符串首元素的指针left和right，再创建两个哈希表hash1和hash2分别存储字符数组words和窗口内的字符串，之后创建一个变量count来表示窗口内的元素个数，在此在字符串进窗口之后判断hash2[in]是否小于等于hash1[in],是的话就将有效元素加一；在字符串出窗口之前判断hash2[in]是否小于等于hash1[in],是的话就将有效元素减一。最后在出窗口之后判断count是否等于words.length()，是的话就将left存储到最后返回的vector对象当中。

该算法的流程图如下所示：

在此count1表示的是数组words 当中的元素个数，count2表示的是窗口内的有效元素个数，gap表示的是数组words当中每个元素所对应的字符串的的长度。

在以上看起来已经将该算法题的所有步骤都已经考虑到了，但其实我们有一个点没有考虑。那就是在以上我们只考虑从s当中的第一个字符开始，但是其实还要考虑起始为gap之前字符的全款。

例如以下示例：

这时如果只考虑从第一个字符开始的情况就最后就只能得到下标0,2,4,6,8,10。那么在此就还要考虑下标从1开始的情况

 

所以以上我们实现的算法流程图也就要做出相应的修改，那就是要将滑动窗口的操作进行gap次，每次滑动窗口的操作left和right的初始值也要作出相应的改变

 

 

代码实现

  1. class Solution {
  2. public:
  3.     vector<int> findSubstring(string s, vector& words) 
  4.     {
  5.         vector<int> ret;
  6.         //创建哈希表hash1存储字符串数组words当中的数据
  7.         unordered_map int> hash1;
  8.         //遍历字符串数组words当中的数据存储到hash2当中
  9.         for(auto& x:words)
  10.             hash1[x]++;
  11.         //变量gap表示字符数组当中每个字符串的长度
  12.         int gap=words[0].size();
  13.         //变量len表示字符串s的长度，变量count1表示字符串数组words的大小
  14.         int len=s.size(),count1=words.size();
  15.         //执行gap次
  16.         for(int i=0;i
  17.         {
  18.             //创建，哈希表hash2存储滑动窗口内的字符串数据
  19.             unordered_map int>hash2;
  20.             //count2表示窗口内的有效元素个数
  21.             int count2=0;
  22.             for(int left=i,right=i;right
  23.             {
  24.                 //进窗口，将right指向的字串进窗口
  25.                 string tmp=s.substr(right,gap);
  26.                 ++hash2[tmp];
  27.                 //在进窗口之后判断进入窗口的字符串是否为有效元素，是的话就count2++
  28.                 if(hash1.count(tmp) && hash2[tmp]<=hash1[tmp])
  29.                 count2++;
  30.                 
  31.                 //判断当前窗口的长度是否大于字符串数组总的字符数，是的话就进行出窗口的操作
  32.                 while((right-left+gap)/gap>count1)
  33.                 {
  34.                     
  35.                     string tmp=s.substr(left,gap);
  36.                     //在出窗口之前判断当前出窗口的字符串是否为有效元素，是的话就将count2--
  37.                     if(hash1.count(tmp) && hash2[tmp]<=hash1[tmp])
  38.                     count2--;
  39.                     //出窗口，将left指向的字串出窗口
  40.                     --hash2[tmp];
  41.                     left+=gap;
  42.  
  43.                 }
  44.                 
  45.                 //判断count1是否等于count2，是的话就将当前下标left插入到ret当中
  46.                 if(count1==count2)
  47.                 {
  48.                     ret.push_back(left);
  49.                 }
  50.  
  51.             }
  52.         }
  53.         //返回vector对象ret
  54.         return ret;
  55.  
  56.         
  57.     }
  58. };

2.7 最小覆盖子串

76. 最小覆盖子串 - 力扣（LeetCode）

 题目解析

通过以上的题目描述就可以看出该算法题要我们实现的是从给定的字符串中找出覆盖字符串t所有字符的最小字串，如果无法从s当中找出满足条件的字串就返回空串。

例如在以上的示例当中s当中所有覆盖字符串t的所有字符的字串如下所示：

通过以上的分析就可以得出在字符串s当中覆盖字符串t的最短字符串是BANC

算法原理讲解

在此在该算法题当中我们可以看到也是在给定的字符串当中寻找满足条件的最小子串，那么根据之前的经验这道算法题也可以使用滑动窗口算法来解决。

这时你可能就会直接想到和之前解决类似的算法题一样创建两个哈希表hash1和hash2分别存储字符串t的字符和窗口内的的字符，创建两个变量count1和count2分别表示t内的字符个数和窗口内的有效字符个数。在进窗口之后判断此时插入到hash2当中的字符是否为有效字符；是的话就将之后当窗口内的有效count2++，在出窗口之前判断此时出的字符是否为有效字符，是的话就将count2--。最后当count1==count2时就进行更新的操作。

以上的算法逻辑确实是可以解决该算法题的，不过在此其实我们还有更好的解决方式就是在窗口内我们统计的不是窗口内有效字符的个数而是去统计窗口内的有效字符种类数，算法的具体改进就是在进窗口之后只有当hash1[in]==hash2[in]时才将count2++，在出窗口之前只有当hash1[out]==hash2[out]时才将count2--，最后当count1==count2时就进行更新

代码实现

统计窗口内有效元素个数版本算法：

  1. class Solution {
  2. public:
  3.     string minWindow(string s, string t) 
  4.     {
  5.         int hash1[128]={0},hash2[128]={0};
  6.         for(auto x:t)
  7.         {
  8.             hash1[x]++;
  9.         }
  10.         int n=s.size(),count=t.size();
  11.         //有效元素个数sum
  12.         int left=0,begin=0,sum=0,len=INT_MAX;
  13.        
  14.         //遍历字符串s
  15.         for(int right=0;right
  16.         { 
  17.             //进窗口
  18.             int in=s[right];
  19.             hash2[in]++;
  20.             //进窗口之前判断当前字符是否为有效字符
  21.             if(hash2[in]<=hash1[in])sum++;
  22.  
  23.             while(sum==count)
  24.             {
  25.                 //当字符串tmp包含字符串t内的所有字符就更新
  26.                 if(right-left+1
  27.                 {
  28.                     begin=left;
  29.                     len=right-left+1;
  30.                 }
  31.                 
  32.                 
  33.                 int out=s[left];
  34.                 //出窗口之前判断当前字符是否为有效字符
  35.                 if(hash2[out]<=hash1[out])
  36.                 {
  37.                     sum--;
  38.                 }
  39.                 hash2[out]--;
  40.                 left++;
  41.  
  42.             }
  43.  
  44.         }
  45.         if(len==INT_MAX)
  46.         return "";
  47.  
  48.         return s.substr(begin,len);
  49.         
  50.     }
  51. };

统计窗口内的有效字符种类数版算法：

  1. class Solution {
  2. public:
  3.     string minWindow(string s, string t) {
  4.         //创建哈希表hash1存储字符串t当中的字符，哈希表hash2存储窗口内的字符
  5.         int hash1[128]={0},hash2[128]={0};
  6.         //count变量表示字符串t当中的字符种类数
  7.         int count1=0;
  8.         for(auto& x:t)
  9.         {
  10.             //当此时x数组下标对应的hash1内的元素值为0就说明插入了新类型的元素就将count1++
  11.             if(hash1[x]==0)count1++;
  12.             hash1[x]++;
  13.         }
  14.         //minlen统计s当中满足条件的最短子串的长度，begin为该子串的起始位置的索引
  15.         int minlen=INT_MAX,begin=-1;
  16.         //count2存储窗口内的有效字符种类数
  17.         int n=s.size(),count2=0;
  18.         for(int right=0,left=0;right
  19.         {
  20.             //进窗口，将此时hash2的in字符下标对应的元素加一
  21.             char in=s[right];
  22.             hash2[in]++;
  23.             //进窗口之后判断当前的进入的字符是否为有效种类的字符，是的话就将count2++
  24.             if(hash2[in]==hash1[in])count2++;
  25.             //判断窗口内的有效个数count2是否和count1相等，是的话就进行出窗口操作
  26.             while(count1==count2)
  27.             {
  28.                 //出窗口之前更新minlen和begin
  29.                 if(right-left+1
  30.                 {
  31.                     begin=left;
  32.                     minlen=right-left+1;
  33.                 }
  34.                 
  35.                 char out=s[left++];
  36.                 //出窗口之前判断当前出窗口的字符是否为有效种类字符，是的话就将count2--
  37.                 if(hash1[out]==hash2[out])count2--;
  38.                 //出窗口
  39.                 hash2[out]--;
  40.             }
  41.  
  42.         }
  43.         //返回子串之前判断进行滑动窗口过程中是否出现符合条件的字串，如果没有就返回空串
  44.         if(begin==-1)
  45.             return "";
  46.         else
  47.             return s.substr(begin,minlen);
  48.         
  49.         
  50.     }
  51. };

 

以上就是本篇的全部内容了，接下来还会带来更多的优选算法的讲解，未完待续……

注：本文转载自blog.csdn.net的mljy.的文章"https://blog.csdn.net/2303_81098358/article/details/144544640"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！