【leetcode】滑动窗口专题

1.长度最小的子数组

leetcode 209.长度最小的子数组

看到这个题目，第一眼肯定想到的是暴力枚举，那我们就来枚举以下试试：

很明显，暴力枚举的方式会超时。

那有没有哪里能优化一下，让它不超时呢？我们来分析一下：

在暴力枚举中，我们的 right 每次都会回到left位置的下一个，然后和 left 一起重新枚举。

优化枚举具体步骤如下：

在上面的枚举过程中，我们的蓝色框就像是一个滑动的、大小不固定的窗口，我们称这种方式叫做滑动窗口

对与滑动窗口而言，无非就以下几个步骤：

每个题目窗口的起始、更新结果的位置是不固定的，具体情况具体分析。

按照滑动窗口的方法，我们的代码就不会超时啦。

简单分析以下时间复杂度：从代码看好像是O(n²)，但是由于我们滑动窗口的思想，两个指针是同向遍历，而且不会回退；当right指针结束时，循环结束，所以它的时间复杂度是O(n)。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int ret = INT_MAX;
        int n = nums.size();
        int sum = 0;
        for(int left = 0, right = 0; right < n; right++)//right后移
        {
            //进窗口
            sum += nums[right];
            //判断窗口
            while(sum >= target)
            {
                //符合条件，更新结果
                ret = min(ret,right - left + 1);
                sum -= nums[left];//出窗口
                left++;
            }  
        }
        if(ret == INT_MAX)
            return 0;
        else
            return ret;
    }
};

2.无重复字符的最长子串

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

这一题首先想到的方法无疑就是枚举，然后统计每个字符出现的次数；如果一个字符出现了两次，那么当前字符对应的字符串就是最长子串

我们发现，暴力枚举法也可以过

那有没有更优的解法呢？我们来分析一下

上述解法不就是滑动窗口吗？

此时的时间复杂度O(n)是不是比暴力枚举O(n²)更加优秀了

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        int hash[128] = { 0 };
        int ret = 0;
        for(int left = 0, right = 0; right < n; right++)
        {
            hash[s[right]]++;//入窗口，先记录当前
            while(hash[s[right]] > 1)//若s[right]重复
            {
                hash[s[left]]--;//出窗口
                left++;
            }
            ret = max(ret,right - left + 1);//更新结果
        }
        return ret;
    }
};

3.最大连续1的个数III

leetcode 1004.最大连续1的个数III

分析题目可知，其中0可以翻转的意思就是：0可以当作1来用。那我们的目标就是找一段包含1的个数最大连续的区间，该区间中0的个数不可以超过k。

这一题的暴力枚举法就不演示了，我们直接上滑动窗口。


这样我们的代码就过咯

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int n = nums.size();
        int zero = 0;//统计0的个数
        int ret = 0;
        for(int left = 0, right = 0; right < n; right++)
        {
            //进窗口，判断是否是0
            if(nums[right] == 0)
                zero++;
            //判断0的个数是否大于k
            while(zero > k)
            {
                //判断是否是0出窗口
                if(nums[left] == 0)
                    zero--;
                left++;
            }
            //更新结果
            ret = max(ret,right-left+1);
        }
        return ret;
    }
};

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

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

通过读题我们可以发现，它一会是左边，一会是右边，是不是很难控制；那应该怎么做呢？
正难则反

• 我们在数组中找一块连续的区间，数组中去除该连续区间的内容，剩下的内容刚好等于x时，那我们是不是就找到了一种情况
• 该连续区间就是数组中元素的总和减去x
• 当在数组中找到的一块连续区间最长时，我们就找到了最佳的解决方案。

还是像前面的题目一样，使用滑动窗口。

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int ret = 0;
        int total = 0;
        int n = nums.size();
        for(auto e : nums)
            total += e; //求数组的和
        int target = total - x; //target为要找的连续区间的总大小

        if(target < 0)//细节
            return -1;
        if(total == x)
            return n;
            
        int sum = 0;
        for(int left = 0, right = 0; right < n; right++)
        {
            sum += nums[right];//进窗口
            while(sum > target)
            {
                sum -= nums[left];
                left++;
            }
            if(sum == target)//找到目标区间，取长的一个
                ret = max(ret,right - left + 1);
        }
        if(ret == 0)
            return -1;
        else
            return n - ret;
    }
};

5.水果成篮

leetcode 904.水果成篮

这个题目这么长，它表达的是什么意思呢？

只有两个篮子，篮子里的水果只能有两种，并且不能跨越树木，求你所经过的树的最多的个数。
那又是求一段连续区间的长度，我们可以使用滑动窗口

那我怎么知道当前摘的水果有几种呢？----使用哈希表统计

我们可以发现，使用哈希表的消耗还是挺大的，能不能再优化一下呢？

由题目要求可知，种类是小于10⁵的，所以我们可以直接使用一个数组+一个变量（记录种类）

这样我们的效率就提升了很多。

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int n = fruits.size();
        int ret = 0;
        int hash[100000] = { 0 };
        int kinds = 0;
        for(int left = 0, right = 0; right < n; right++)
        {
            if(hash[fruits[right]] == 0)//判断是否是新种类水果
                kinds++;

            hash[fruits[right]]++;//进窗口
            
            while(kinds > 2)//判断总类是否大于2
            {
                hash[fruits[left]]--;//出窗口
                if(hash[fruits[left]] == 0)
                    kinds--;  //去除该种类
                left++;
            }
            ret = max(ret,right - left + 1);
        }
        return ret;
    }
};

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

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

分析题目可知，就是在s串中找出p串（p串中的字符顺序可打乱）。
那我们就可以找一个长度和p相等，且字符种类、个数和p串相等的子串即可。

所以我们可以使用两个哈希表，分别统计p串和s串中字符的种类和个数。

那我们先使用暴力枚举的方式试一下：

那两个哈希表是如何进行比较的呢？

1. 首先使用hash1记录p串中字符的类型个数
2. 遍历s，找长度和p相等的子串，同时hash2存放当前字符
   a、若hash2[right] <= hash1[right]时，“有效字符”种类增加
   b、若hash2[right] > hash2[right]，“有效字符”种类不变

暴力枚举的方式确实可以过，但效率比较低下。
既然是找一段连续的区间，那能不能使用滑动窗口呢？我们来试一下

这样我们的效率就高很多了

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        int len = p.size();
        int hash1[128] = { 0 };
        for(auto e: p)
            hash1[e]++;//统计p串的种类
        int n = s.size();
        int hash2[128] = { 0 };//统计子串种类
        int kinds = 0;
        int tmp = 0;
        for(int left = 0,right = 0; right < n ; right++)
        {
            hash2[s[right]]++; //进窗口
            tmp++;//子串长度增加
            if(hash2[s[right]] <= hash1[s[right]])
                kinds++;//"有效字符"种类增加
            if(tmp > len)
            {
                if(hash2[s[left]] <= hash1[s[left]])
                    kinds--;//left位置为“有效字符”，种类减少
                hash2[s[left]]--;
                tmp--;
                left++;
            }
            if(tmp == len)
                if(kinds == len)
                    ret.push_back(left);
        }
        return ret;
        
    }
};

7.串联所有单词的子串

leetcode 30.串联所有单词的子串

这一题和前一道题目类似，只不过这里是将字符换成了字符串而已。因此我们还是使用：滑动窗口+哈希表的方式解决。

解题步骤：

1. 先使用hash1统计words中字符串的种类
2. 使用滑动窗口(由于字符串的长度是固定的，所以可以直接跳跃长度)
   a、定义起始：left、right
   b、字符串进窗口，需要使用字符串的函数substr进行裁剪
   c、判断字符串的种类
     是否出窗口
     更新结果

然而，代码只过了一部分，分析一下它的测试用例发现，

这样代码就过啦！

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string,int> hash1;
        for(auto& e : words)
            hash1[e]++;//统计要求的字符串种类
        int n = s.size();
        int len = words[0].size();//固定的字符串长度
        int m = words.size();//数组长度
        for(int i=0; i < len; i++)
        {
            unordered_map<string,int> hash2;
            int count = 0;
            for(int left = i, right = i; right <= n -len; right+= len)
            {
                string in = s.substr(right,len);//裁剪字符串
                hash2[in]++;//进窗口
                if(hash2[in] <= hash1[in])
                    count++;//统计当前字符串数量
                if(right - left + 1 > m*len)//判断字符串数量是否大于字符数组
                {
                    string out = s.substr(left,len);
                    if(hash2[out] <= hash1[out])
                        count--;
                    hash2[out]--;//出窗口
                    left += len;
                }
                if(count == m)
                    ret.push_back(left);
            }
        }
        return ret;
    }
};

8.最小覆盖子串

leetcode 76.最小覆盖子串

该题和上一题的解题思路差不多，也是在s串中找t串的全部字符，只不过这里要将找到的字符串的最小的一个返回而已。

我们依旧使用滑动窗口+哈希表的方式解决。

1. 使用hash1统计t串中字符的种类和数量
2. 滑动窗口：定义起始位置 left, right
   a、进窗口
   b、判断是否出窗口
   c、更新结果（仅需记录串的起始位置和长度，最后在切割子串）

在代码中在记录字符串的起始位置和长度即可，这样我们的代码就过啦。

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = { 0 };
        for(auto e : t)
            hash1[e]++;//统计t串的字符种类和数量
        int m = t.size();
        int n = s.size();
        int hash2[128] = { 0 };
        int count = 0;
        int start = 0;
        int len = INT_MAX;
        for(int left = 0, right = 0; right < n; right++)
        {
            hash2[s[right]]++;//进窗口
            if(hash2[s[right]] <= hash1[s[right]])//是否更新有效字符
                count++;
            while(count >= m)//是否出窗口
            {
                if(count == m)//找到符合种类的子串
                {
                    //取长度小的一个
                    int curlen = right - left + 1;
                    if(curlen < len)
                    {
                        start = left;
                        len = curlen;
                    }
                }
                //出窗口
                if(hash2[s[left]] <= hash1[s[left]])
                    count--;
                hash2[s[left]]--;
                left++;
            }
        }
        if(len == INT_MAX)
            return "";
        else
            return s.substr(start,len);
    }
};