算法——滑动窗口

1. 什么是滑动窗口？

滑动窗口算法是一种解决数组或列表中子数组或子序列问题的有效方法。该算法通过定义一个窗口，然后在数据结构上滑动该窗口，逐步处理数据，以解决特定类型的问题。其基本思想是维护一个窗口，初始时窗口覆盖数组中的一部分元素，然后通过滑动窗口来依次处理每个子数组。在每次窗口滑动时，可以通过添加新元素和删除旧元素来更新窗口的内容，以在O(1)时间内完成操作。

2. 滑动窗口的大致解题流程

滑动窗口实际上是双指针算法的一个延伸，它特指双指针算法中的同向双指针，在这里我们以一道例题来讲解滑动窗口类型的大致解题流程，例题如下：209. 长度最小的子数组 - 力扣（LeetCode）

由于在实际的做题中，我们并不能总是直接判断这道题能用什么算法，因此我们可以先用暴力解法解决这道题，即固定一个左指针，从左指针的位置向右遍历数组，遍历到和为target为止（第一个即可），随后将左指针右移，再次执行上述操作，随时统计最小的区间，稍微分析这个算法我们可以发现它的时间复杂度是O(N^2)的，在这个过程中我们可以看到，整个数组是严格单调的且指针移动方向是相同的，此时我们就可以采取滑动窗口的思想来解决，滑动窗口一般流程如下

1. 进窗口

2. 判断

        出窗口

3. 在合适的位置更新结果

在这道题中我们可以发现，当右指针处于一个新位置时，将其所在元素入窗口，直到sum（窗口内元素和）>= target时，将左指针位置出窗口，并记录当前区间 ，稍加分析可以发现更新结果的位置应该在出窗口前，这样的话我们可以得到如下代码

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

3. 应用实例

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

题目链接：3. 无重复字符的最长子串 - 力扣（LeetCode）

解析：分析题目我们可以发现，这道题是要寻找最长的不含重复字符的子串，我们可以采取哈希表统计字符个数，滑动窗口控制子串长度的操作，分析一下可以知道，当right处于一个新位置就将其入窗口，若当前字符的出现次数 > 1则表明当前字符串出现重复字符，此时让left所在位置的元素出窗口，直到当前字符出现次数 == 1，显然，更新结果应在出窗口后，代码如下

class Solution 
{
public:
    int lengthOfLongestSubstring(string s) 
    {
        int len = 0, n = s.size();
        unordered_map<char, int> hash;
 
        for (int left = 0, right = 0; right < n; right++)
        {
            char in = s[right];
            hash[in]++;
            while (hash[in] > 1)
            {
                char out = s[left++];
                hash[out]--;
            }
            len = max(len, right - left + 1);
        }
 
        return len;
    }
};

2. 最大连续1的个数

题目链接：485. 最大连续 1 的个数 - 力扣（LeetCode）

解析：分析题目我们可以发现，这道题是要寻找最长的只含有1的数组，我们可以直接滑动窗口统计长度的操作，分析一下可以知道，当right处于1的位置就将其入窗口，若right处于0的位置，则表明当前数组不是仅含有0的数组，此时让left=right+1出窗口，显然，更新结果应在出窗口前，代码如下

class Solution 
{
public:
    int findMaxConsecutiveOnes(vector<int>& nums) 
    {
        int len = 0, n = nums.size();
 
        for (int left = 0, right = 0; right < n; right++)
        {
            if (nums[right] == 1) len = max(len, right - left + 1);
            else left = right + 1;
        }
 
        return len;
    }
};

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

题目链接：1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

解析：对于这道题分析后我们可以发现，正面解决可能比较困难，此时我们就可以采取正难则反的思想，这道题是要寻找将x减到0的最小操作数，换而言之，就是寻找值为sum-x的最长连续子区间，我们可以使用滑动窗口来寻找指定区间，分析一下可以知道，当right处于一个新位置就将其入窗口，若当前区间的总和 >= sum-x，则表明当前数组可能是一个合理区间，此时让left所在位置的元素出窗口，直到当前区间总和 < sum-x，显然，更新结果应在出窗口前，代码如下

class Solution 
{
public:
    int minOperations(vector<int>& nums, int x) 
    {
        int sum = 0, n = nums.size(), len = INT_MIN;
        for (auto& e : nums) sum += e;
        if (sum == x) return n;
        int target = sum - x;
        if (target < 0) return -1;
 
        int v_sum = 0;
        for (int left = 0, right = 0; right < n; right++)
        {
            v_sum += nums[right];
            while (left < n && v_sum >= target)
            {
                if (v_sum == target) len = max(len, right - left + 1);
                v_sum -= nums[left++];
            }
        }
 
        return len == INT_MIN ? -1 : n - len;
    }
};

4. 水果成篮

题目链接：904. 水果成篮 - 力扣（LeetCode）

解析：简单翻译一下这道题的题意就是仅能有2种树被采摘，求最多能采摘多少树，显然我们可以使用滑动窗口 + 哈希表的解法，分析一下可以知道，当right处于一个新位置就将其入窗口，若当前哈希表中的种类数量 > 2，则表明当前这些树超过了2个种类，此时让left所在位置的元素出窗口，直到哈希表中的种类数量 == 2，显然，更新结果应在出窗口后，代码如下

class Solution 
{
public:
    int totalFruit(vector<int>& fruits) 
    {
        unordered_map<int, int> hash;
        int n = fruits.size();
 
        int num = 0;
        for (int left = 0, right = 0; right < n; right++)
        {
            int in = fruits[right];
            hash[in]++;
            while (hash.size() > 2)
            {
                int out = fruits[left++];
                hash[out]--;
                if (hash[out] == 0) hash.erase(out);
            }
            num = max(num, right - left + 1);
        }
 
        return num;
    }
};

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

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

解析：对于这道题我们是要在s中找到所有p的异位词，即需要遍历一遍s，我们可以使用两个哈希表，来分别统计s与p中对应字符的个数，当right处于新位置时入窗口，当当前窗口大小size > p.size时，让left所处位置出窗口，更新结果当然是在出窗口后，代码如下

class Solution 
{
public:
    vector<int> findAnagrams(string s, string p) 
    {
        vector<int> ret;
        int hash1[26] = {0};
        for (auto ch : p) hash1[ch-'a']++;
        int hash2[26] = {0};
 
        for (int left = 0, right = 0; right < s.size(); right++)
        {
            char in = s[right];
            hash2[in - 'a']++;
            if (right - left + 1 > p.size()) hash2[s[left++]-'a']--;
            if (check(hash1, hash2)) ret.push_back(left);
        }
 
        return ret;
    }
 
    bool check(int* hash1, int* hash2)
    {
        for (int i = 0; i < 26; i++)
            if (hash1[i] != hash2[i]) return false;
        
        return true;
    }
};

此外，我们可以对这个算法进行一个优化——即使用变量count来统计有效字符数，即当一个right即将入窗口时，若hash2中它所对应的字符 < hash1中它所对应的字符时，count++，当一个left即将出窗口时，若hash2中它对应的字符 <= hash1中它所对应的字符时，count--，代码如下

class Solution 
{
public:
    vector<int> findAnagrams(string s, string p) 
    {
        int count = 0;
        vector<int> ret;
        int hash1[26] = {0};
        for (auto ch : p) hash1[ch-'a']++;
        int hash2[26] = {0};
 
        for (int left = 0, right = 0; right < s.size(); right++)
        {
            char in = s[right];
            if (hash2[in-'a'] < hash1[in-'a']) count++;
            hash2[in-'a']++;
            if (right - left + 1 > p.size())
            {
                char out = s[left++];
                if (hash2[out - 'a'] <= hash1[out-'a']) count--;
                hash2[out-'a']--;
            }
            if (count == p.size()) ret.push_back(left);
        }
 
        return ret;
    }
};

6. 串联所有单词的子串

题目链接：30. 串联所有单词的子串 - 力扣（LeetCode）

解析：由于word中所有字符串长度相等，我们可以计算出word.lenth * word[i].lenth来计算出排列总数，然后再使用count计数的原理（详见上题结尾），在一个right（这里的right代指一串子串）入窗口时，若hash2[right] < hash1[right]则count++，当窗口长度 > word.lenth * word[i].lenth时，让left出窗口，若hash2[left] <= hash1[left]则count--，结果在出窗口后更新，代码如下

class Solution 
{
public:
    vector<int> findSubstring(string s, vector& words) 
    {
        int len = words.size() * words[0].size();
        unordered_mapint> hash1;
        for (auto& s : words) hash1[s]++;
        int n = s.size();
        vector<int> ret;
 
        for (int i = 0; i < words[0].size(); i++)
        {
            unordered_mapint> hash2;
            int count = 0;
            for (int left = i, right = i; right < n; right += words[0].size())
            {
                string in = s.substr(right, words[0].size());
                // 使用hash1.count(in)可以避免创建新的映射关系，从而提高效率
                if (hash1.count(in) && hash2[in] < hash1[in]) count++;
                hash2[in]++;
                if (right - left + 1 > len)
                {
                    string out = s.substr(left, words[0].size());
                    if (hash2[out] <= hash1[out]) count--;
                    hash2[out]--;
                    left += words[0].size();
                }
                if (count == words.size()) ret.push_back(left);
            }
        }
 
        return ret;
    }
};

7. 最小覆盖子串

题目链接：76. 最小覆盖子串 - 力扣（LeetCode）

解析：分析这道题我们可以发现，这道题是要在s中寻找最小的子串使他能覆盖t，我们可以使用滑动窗口来寻找指定区间，哈希表来统计对应字符出现个数，分析一下可以知道，当right处于一个新位置就将其入窗口，若当区间有效字符种类数count==kind（t中字符种类个数），则表明当前子串属于合理区间，此时让left所在位置的元素出窗口，直到当前区间有效字符count < kind，显然，更新结果应在出窗口前，代码如下

class Solution 
{
public:
    string minWindow(string s, string t) 
    {
        if (s.size() < t.size()) return "";
        int kind = 0;
        int hash1[126] = {0};
        for (auto ch : t) if (hash1[ch]++ == 0) kind++;
        int hash2[126] = {0};
        int len = INT_MAX, begin = -1; 
 
        for (int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            char in = s[right];
            hash2[in]++;
            if (hash2[in] == hash1[in]) count++;
            while (count == kind)
            {
                if (right - left + 1 < len)
                {
                    len = right - left + 1;
                    begin = left;
                }
                char out = s[left++];
                if (hash2[out] == hash1[out]) count--;
                hash2[out]--;
            }
        }
 
        if (begin == -1) return "";
        else return s.substr(begin, len);
    }
};