滑动窗口算法——部分OJ题详解

关于滑动窗口

部分OJ题详解

209.长度最小的子数组

3.无重复字符的最长字串

1004.最大连续1的个数Ⅲ

1658.将x减到0的最小操作数

904.水果成篮

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

30.串联所有单词的子串

76.最小覆盖子串

关于滑动窗口

其实滑动窗口也是通过双指针来实现，但是和双指针算法不同的是，滑动窗口的算法是两个指针同时移动，没有快慢之分，而通过对两个指针在数组中围出来的一个“区域”做操作，我们称为“滑动窗口算法”，我们通过下面8个OJ题来学习下：

①什么是滑动窗口

②什么时候使用滑动窗口

③滑动窗口为什么能正确地解决这个问题斯滑动窗口地时间复杂度

④滑动窗口如何用代码实现

部分OJ题详解

209.长度最小的子数组

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

解释下这道题：给一个整数数组nums，和一个数target，找出数组中满足和大于等于target的长度最小的连续子数组，返回长度，没有返回0，通过示例能很简单理解，下面我们来分析下这道题：

首先是暴力解法，用两个for循环穷举所有的子数组，然后将数组的值依次相加，所以两个for循环，再加上求和的时候又一个循环，所以时间复杂度为O(N^3)
所以要优化暴力算法，使用“同向双指针”来优化，并且题目也说了，正整数数组，这代表加的数越多，值越大 --> 符合单调性的特征
假设数组为[2, 3, 1, 2, 4, 3]，target=7。定义left指针指向2，right也指向2，定义一个sum=nums[right]记录两个指针中间所有值的和。刚开始sum=2，小于target，于是right++，一直小于7就一直right++，直到right指向第二个2时，sum=8，大于target，满足条件，记录当前长度len = right - left，然后left++继续判断。这个“同向双指针”就是我们说的“滑动窗口”
如何使用滑动窗口呢？步骤：①定义双指针left=0，right=0 ②进窗口 ③出窗口（23步重复）
以上面的第三点为例，第一步就是定义双指针，第二步就是判断滑动窗口内的和sum，如果sum小于7那么right++（进窗口，也就是扩大窗口右边界），如果sum大于等于7，先记录长度然后left++，sum-=nums[left-1]（出窗口，也就是缩小窗口左边界），直到right到达数组结尾就退出循环
简单来说就是，sum小于target就进窗口right++，sum大于等于target就出窗口left++，所以整个滑动窗口提高效率就是利用单调性，规避了很多没有必要的枚举，最终整个过程就是left和right只把数组遍历了一遍，时间复杂度为O(2N) == O(N)

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, right = 0, len = INT_MAX;
        int n = nums.size(), sum = 0;
        while(right < n)
        {
            sum += nums[right];
            while(sum >= target)
            {
                len = min(len, right - left + 1); //更新长度
                sum -= nums[left++];
            }
            right++;
        }
        if(len == INT_MAX) return 0;
        else return len;
    }
};

3.无重复字符的最长字串

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

解释下这道题：给一个字符串，找出不含有重复字符的最长字串的长度，假设输入s="abcabcbb"，因为无重复字符的最长字串是“abc”，所以返回3，s="bbbb"，返回1；s="pwwkew"，返回3，因为“wke”。下面我们来分析下这道题：

首先是暴力解法，以一个字符“a”为起点，依次往后枚举所有情况，遇到相同的字母“a”，记录长度，再固定b再次枚举，可以结合哈希表，判断字符是否重复出现，时间复杂度为O(N^2)
我们依然可以用滑动窗口优化暴力解法，假设字符串数组为[d, e, a, b, a, a, b, c, a]，定义双指针，刚开始left和right都指向“d”，然后把d扔哈希表里面去，right++，每走一步，就把值扔哈希表里面去。当right走到第二个“a”时，判断哈希表时发现表中已经有“a”了，于是记录当前长度len = right - left + 1，然后left一直++，直到left跳过第一个“a”的位置，然后right++再判断，重复上面的操作
所以步骤大致为三步：①left = 0， right = 0 ②进窗口，把right指向的字符串扔哈希表里去，right++ ③当把right扔哈希表里时发现是重复字符，记录长度，然后出窗口，left++一直到第一个重复字符后面，更新结果，然后循环再次right++重复步骤②

class Solution 
{
public:
    int lengthOfLongestSubstring(string s) 
    {
        int hash[128] = {0}; //用数组来模拟哈希表，数字为0就未出现，为1就是出现了一次，为2就是出现了两次
        int left = 0, right = 0, n = s.size(), ret = 0;
        for(; right < n; right++)
        {
            //进窗口，把字符扔哈希表里去
            hash[s[right]]++;
            while(hash[s[right]] > 1) //判断在数组中该字符是否出现两次，如果是就出窗口，让left位置的字符离开哈希表，left再右移
            {
                hash[s[left]]--; //left一直往后减，直到减去重复字符的第一个
                left++;
            }
            ret = max(ret, right - left + 1); //更新最后结果
        }
        return ret;
    }
};

1004.最大连续1的个数Ⅲ

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

解释下这道题：给一个数组，其只有“1”和“0”两种数，再给一个数K，表示在这个数组中最多可以把K个0变成1，请判断最长的连续1的最大个数。下面来分析下这道题：

这道题用正常的思路来看，找出最长的连续的1的个数，其实很难很难，所以我们可以换个角度思考：我们其实只需要找出一个区域，使得这个区域的0的个数不超过K个就可以了，所以这道题可以转化为：找出0的个数不超过K个的最长子数组长度
首先是暴力解法 + zero计数器：定义两个指针，一个起点一个终点，依次枚举起点到终点的子数组，当zero技术大于K时，记录当前子数组长度，然后left++，right+left+1 继续检测
暴力解法肯定会超时，所以我们可以用滑动窗口来优化暴力解法。暴力解法是left++后，再次枚举，但是其实可以不必再枚举，可以让left一直++，直到left经过第一个0后才停下来，然后再right=left+1
步骤还是三步：①定义双指针left = 0，right = 0 ②进窗口：当right为1时不管，当right为0时，计数器++ ③出窗口：当计数器大于K时，先记录长度，left一直右移，每次移动判断是否为0，当为0时，跳过后停止，计数器--

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int left = 0, right = 0, ret = 0, n = nums.size();
        int zeroNum = 0; //0计数器
        while(right < n)
        {
            if(nums[right] == 0) zeroNum++;
            while(zeroNum > k) //判断
            {
                if(nums[left] == 0)
                {
                    zeroNum--;
                }
                left++;
            }
            ret = max(ret, right - left + 1); //更新结果
            right++;
        }
        return ret;
    }
};

1658.将x减到0的最小操作数

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

解释下这个题目：给一个整数数组nums和一个整数x，每次操作时只能从数组两端进行操作，使得最左边或最右边的值相加后是否等于x，可以使用多个数，如果恰好等于x则返回使用数的个数，如果不能返回-1，并且每次使用完一个数后要在原数组上把该数删掉，下面我们来分析下这道题：

这道题和上面的求“最大连续1的个数”一样，正面看很难，但是所谓“正难则反”，我们也可以从另一个角度来看这题：我们可以把左边的区间的数计算和为a，右边区间计算和为b，要使得a+b=x，但是我们可以反过来，只要保证中间区域的连续区间的和c=sum-x即可（sum为为该数组所有元素的和），要求的是两边最小的区间，那么反过来就是求最大中间区间长度
所以这道题可以转化为：求最长的连续区间，使得区间的和正好等于sum-x
首先是暴力解法：先定义双指针left=0，right=0，计算target=sum-x，ret += nums[right++]，当ret == target时，记录长度然后left++，right = left+1重置双指针后继续遍历计算
暴力解法肯定是超时，所以我们可以用滑动窗口来优化：当ret == target时，right不要动，left一直++并且ret-=nums[left]，每次都做判断，当ret小于target时，right++然后再判断，当ret == target时就计算返回值
所以步骤也是三个：①定义双指针 ②进窗口，sum += nums[right] ③出窗口，判断如果sum>target时，一直出窗口，也就是一直sum -= nums[left++]，直到sum小于target才回归步骤②；如果sum = target，记录长度然后尝试返回

class Solution {
public:
    int minOperations(vector<int>& nums, int x)
    {
        int left = 0, right = 0, sum = 0, n = nums.size();
        int ret = 0; //计算滑动窗口中间的和
        for(auto e : nums) sum += e; //计算数组总和
        int target = sum - x; //计算判断值
        if(target < 0) return -1;
        
        int a = -1; //要返回的值
        while(right < n)
        {
            ret += nums[right]; //先雷打不动，进窗口
            while(ret > target) //滑动窗口的值大于判断值时，出窗口
            {
                ret -= nums[left];
                left++;
            }
            if(ret == target) 
            {
                a = max(a, right - left + 1);
            }
            right++;
        }
        return a == -1 ? -1 : n - a; 
    }
};

904.水果成篮

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

原题比较长，简单解释下：就是在一个数组中找一个连续的子数组，使该子数组只能有一种或两种数组，返回可以找到的最长的子数组的长度，下面我们拉分析下这道题：

暴力解法还是暴力枚举 + 哈希表，穷举所有符合条件的子数组然后找到最长的，返回最长的长度
接着我们用滑动窗口来优化，先定义双指针left = right = 0，然后进窗口，把right的值扔哈希表里去使该数的数量++，然后是出窗口，先判断扔进去哈希表里的数的种类是否大于2，如果大于2，先把该数在哈希表里的数量--，然后left++，当哈希表里的两个数有一个为0时，left停止++，更新结果

class Solution {
public:
    int totalFruit(vector<int>& f) 
    {
        int left = 0, right = 0, n = f.size(), ret = 0;
        int kind = 0; //统计窗口内水果种类
        int hash[100001] = {0}; //依旧用数组来代替哈希表
        while(right < n)
        {
            if(hash[f[right]] == 0) kind++; 
            hash[f[right]]++;
            while(kind > 2) //当种类大于2时，一直出窗口，使kind恢复成2
            {
                hash[f[left]]--; 
                if(hash[f[left]] == 0) kind--; //当哈希表该位置水果数量为0时，
                left++;
            }
            ret = max(ret, right - left + 1);
            right++;
        }
        return ret;
    }
};

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

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

这道题标着中等，其实已经有了困难的难度了，下面解释下题目：给两个字符串s和p，找到s种所有p的异位词，返回这些字串的起始索引，不考虑输出顺序（异位词：指由相同字母重新排列组合形成的字符串）

①假设s="cbaebabacd" p="abc" 输出[0, 6] 因为起始索引0的字串是"cba"，是"abc"的异位词；而且起始索引6的字串是"bac"，也是"abc"的异位词
②s="abab" p="ab" 输出[0, 1, 2] 因为起始索引012的字串分别位"ab""ba""ab"，都是"ab"的异位词

下面我们来分析下这道题：

先处理一个小问题：如何快速判断两个字符串是否是异位词？我们可以先把两个字符串用双指针排序，但是时间复杂度为O(NlogN + N)，太耗时；所以由于我们不关心是顺序，只关心字符个数是否就绪，所以我们依旧可以用哈希表来搞，把p字符串全扔哈希表里去，然后s字符串也扔哈希表，只要判断两个哈希表里的字符个数是否一样就可以了
暴力解法：把p的字符扔hash1，长度为m，然后我们在s穷举所有长度为m的字串，把字串扔哈希表里去，每扔完一个字串就比较下两个哈希表的内容是否相同即可，比较完后清空hash2
优化暴力解法：当有列举子数组或者列举字串时，肯定要想到滑动窗口。假设s字符串为“c b a e b a b a c d”，p为“a b c”。当用暴力枚举时，我们先只枚举开始的两个字串“c b a”与“b a e”，比较下两个字串，可以发现除了字符“c” “e”，中间的“b a”是一样的，已经在哈希表中存在，所以只需要把第一个字符从哈希表中删除，把下一个字符添加进哈希表就完成了下一次枚举
因此第二次枚举时，没有必要重新从第二个位置添加三个字符到哈希表，下一次枚举也是，把第一个字母添加进哈希表，把下一个字母扔进去，就可以用滑动窗口来解决这个问题
以s字符串为“c c b a e b a b a c d”，p为“a b c”为例。刚开始left和right都指向第一个c，然后先把p的三个字符放到hash1里去，并且数量都为1，然后把c扔进hash2，那么c的个数变为1，然后与hash1的c的数量做对比，此时1<=1所以为”有效字符“，count++。当right++后，c的数量变为了2，2>1，不符合有效字符，count不变，right继续++
right指向b时，符合条件，count再++，right指向a，count再++。这时窗口长度为4了，left++，这时候如果left-1的字符的数量>1，那么表示该left-1的字符“c”是多余字符，删掉；hash2的c的数量变为1，然后该窗口已经符合要求，记录left的值，count不更新，然后right再++指向e，由于hash1没有e，此时count不做处理，此时窗口长度为4了，left++，但是left-1为有效字符，hash2中c的数量变为0，count--
所以大致步骤就是：①进窗口：进入后，hash2[in] <= hash1[in]，如果符合条件，count++，不符合count不变 ②判断是否出窗口：出去前，hash2[out] <= hash1[out]，如果符合条件，count--，不符合count不变 ③更新结果：如果count == m，输出left

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int hash1[26] = { 0 }; //存储p字符串中字符的数量
        int hash2[26] = { 0 }; //存储s字符串中字符的数量
        for(auto e : p) hash1[e - 'a']++; //把p先扔hash1里去用于判断异位词
        int len = p.size(); //定义滑动窗口大小，也就是字符串p的长度
        
        vector<int> v; //存储符合条件的索引值，用于返回
        int left = 0, right = 0, n = s.size();
        int count = 0; //表示有效字符个数
        while(right < n)
        {
            char in = s[right]; //in表示该次循环中滑动窗口最后一次进入窗口的字符
            hash2[in - 'a']++; //把in字符扔哈希表里，也就是让对应字符的位置数量++
            if(hash2[in - 'a'] <= hash1[in - 'a']) count++; //如果滑动窗口中的该字母与p中的某个字母一样，那么表示有效字符+1
            if(right - left + 1 > len) //判断窗口长度是否等于len，如果窗口大于len了，那么出窗口，left++并移除哈希表中该字母，维护count
            {
                char out = s[left++]; //表示出窗口的字母，也就是滑动窗口的前面一个字母
                if(hash2[out - 'a'] <= hash1[out - 'a']) count--; //表示如果出窗口的字母与p字符串中字母种类相同且数量小于p中的，那么表示该字符为有效字符，移除有效字符，count--
                hash2[out - 'a']--; //移除hash2中该元素，就是将该元素的在哈希表中的数量--
            }
            if(count == len) v.push_back(left); //有效字符个数符合p的长度，表示滑动窗口中字符的种类和数量与p字符串，符合异位词条件
            right++;
        }
        return v;
    }
};

30.串联所有单词的子串

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

这道题和上面那一道很相似，下面来解释下这道题：给一个字符串s和一个字符串数组words，words中所有字符串的长度相同。假设s="barfoothrfoobarman" words={"foo", "bar"} 返回[0, 9] 因为0开始的字符串是barfoo，从9开始的字符串是foobar，是words中所有字符串以任意顺序排列连接起来的字串，如果没有结果则返回空数组，，下面来分析下这道题：

就上面的为例，words中每个字符串的长度为3，那么我们可以对s字符串进行处理，我们把s字符串每三个字符进行划分，每三个字符看成一个字符，那么就和上一道题的“找出所有字母的异位词”的那个题目一样了。但是由于该题有顺序要求，所有不能一股脑全扔哈希表里去，得采取一些策略
这道题与上个题目不一样的地方：①哈希表不能再用数组了，要用真的哈希表，可以用unordered_map<string, int> 来定义hash1和hash2 ②left和right每次移动时，不再只++一次了，而应该 += 单词的长度len ③滑动窗口的执行次数也是len次，除此之外其余操作和上题一样

class Solution 
{
public:
    vector<int> findSubstring(string s, vector<string>& words) 
    {
        vector<int> v;
        unordered_map<string, int> hash1; //保存words内所有单词的频次
        for(auto& s : words) hash1[s]++;
        int len = words[0].size(); //每个单词的长度
        int n = words.size(); //字符串数组中字符串的数目
        for(int i = 0; i < len; i++) //执行len次滑动窗口的次数
        {                                    
            unordered_map<string ,int> hash2; //保存窗口内所有单词的频次
            for(int left = i, right = i, count = 0; right + len <= s.size(); right += len) /* 移到最后时，把最后一个长度为len的单词也加进去后，不能再往后移动了 */
            {   
                //进窗口 + 维护count
                string in = s.substr(right, len); //in是即将进入窗口的字符串
                hash2[in]++;
                if(hash1.count(in) && hash2[in] <= hash1[in]) count++; //如果加进hash2后该单词的频次小于hash1的，那么该单词就是有效字符
                //判断，当窗口大小大于字符串总长度，就要出窗口 + 维护count
                if(right - left + len > len * n)
                {
                    string out = s.substr(left, len);
                    if(hash1.count(out) && hash2[out] <= hash1[out]) count--; //如果hash2里该单词的频次小于hash1里的，那么要出窗口的单词是有效字符，count要--
                    hash2[out]--;
                    left += len;
                }
                //更新结果
                if(count == n) v.push_back(left);
            }
        }
        return v;
    }
};

76.最小覆盖子串

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

该题标着困难难度，但其实难度远没有上面两题高，这题最多算中等难度，下面来解释下题目：给给一个字符串s，一个字符串t，返回s中覆盖t所有字符的最小字串，如果不存在就返回空串。

注意：t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符的数量，如果s中存在这样的子串，我们保证它是唯一的答案

s="ADOBECODEBANC" t="ABC" 输出"BANC，因为ADOBEC包含ABC，后面的BANC也包含，但是后面的字串比前面短，所以返回后面那个BANC

下面来分析下这道题：

首先还是暴力算法，还是暴力枚举出所有的连续字串，然后两个哈希表比较即可
现在对暴力算法进行优化：还是left和right，当两个指针的区域符合要求时，left，然后right=left+1重新遍历，这是暴力算法，但是其实right没必要先回去，先分析下要不要回去，left++后有两种结果：①left++后，区域仍符合要求，那么right可以不动，left继续++然后再次判断 ②当left++后不符合要求，right也可以不回去，right就一直往后走直到符合要求，这个操作前面已经见过很多了，就是利用了单调性
前面也说过，只要看到是列举子字符串或子数组等子的，都可以考虑用滑动窗口，然后只要是涉及到“覆盖”，“查找相同”类似的，都可以用哈希表来搞，所以下面就是用“滑动窗口” + “哈希表”来解决这道题
滑动窗口的步骤绝大多数清空下都是那三个：①定义双指针：left = 0， right = 0 ②进窗口：把right扔哈希表里去，然后和上面几道题一样维护有效字符计数count，也就是当hash2(in) 时如果符合条件，那么count++ ③然后还是判断 + 出窗口：如果hash2中的t字符数量都 >= hash1的字符时，就出窗口，left++，然后if(hash2(out) == hash1(out) ) count--，最后如果count符合要求count == hash1.size()，那么就更新结果

class Solution 
{
public:
    string minWindow(string s, string t) 
    {
        int hash1[128] = { 0 }; //统计t字符串中每一个字符的频次
        int hash2[128] = { 0 }; //统计窗口内每一个字符的频次
        int kinds = 0; //统计有效字符有多少种
        for(auto ch : t)  if(hash1[ch]++ == 0) kinds++; //统计有效字符种类时顺便把字符扔哈希表里去

        int minlen = INT_MAX, begin = -1;
        for(int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            char in = s[right];
            if(++hash2[in] == hash1[in]) count++;
            while(count == kinds) //判断
            {
                if(right - left + 1 < minlen) //当有比原来字符串长度更短的字符串时，更新结果
                {
                    minlen = right - left + 1;
                    begin = left;
                }
                char out = s[left++];
                if(hash2[out]-- == hash1[out]) count--;
            }
        }
        if(begin == -1) return "";
        else return s.substr(begin, minlen);
    }
};