算法——滑动窗口

1. 什么是滑动窗口？

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

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

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

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

1. 进窗口

2. 判断

        出窗口

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

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

class Solution {public:    int minSubArrayLen(int target, vector& nums)     {        int len = INT_MAX;        int n = nums.size(), sum = 0;        for (int left = 0, right = 0; right = 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 hash;        for (int left = 0, right = 0; right  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& nums)     {        int len = 0, n = nums.size();        for (int left = 0, right = 0; right  
3. 将x减到0的最小操作数
 
题目链接：1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）
  
解析：对于这道题分析后我们可以发现，正面解决可能比较困难，此时我们就可以采取正难则反的思想，这道题是要寻找将x减到0的最小操作数，换而言之，就是寻找值为sum-x的最长连续子区间，我们可以使用滑动窗口来寻找指定区间，分析一下可以知道，当right处于一个新位置就将其入窗口，若当前区间的总和 >= sum-x，则表明当前数组可能是一个合理区间，此时让left所在位置的元素出窗口，直到当前区间总和  
class Solution {public:    int minOperations(vector& 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 = 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& fruits)     {        unordered_map hash;        int n = fruits.size();        int num = 0;        for (int left = 0, right = 0; right  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 findAnagrams(string s, string p)     {        vector ret;        int hash1[26] = {0};        for (auto ch : p) hash1[ch-'a']++;        int hash2[26] = {0};        for (int left = 0, right = 0; right  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  
此外，我们可以对这个算法进行一个优化——即使用变量count来统计有效字符数，即当一个right即将入窗口时，若hash2中它所对应的字符