【基础算法总结】滑动窗口

算法原理：

解法1：暴力枚举，O(N^2)。从前往后枚举数组中的任意⼀个元素，把它当成起始位置。然后从这个起始位置开始，然后寻找⼀段最短的区间，使得这段区间的和⼤于等于⽬标值。将所有元素作为起始位置所得的结果中，找到最⼩值即可。绝对超时。

解法2：滑动窗口，O(N)。让滑动窗⼝满⾜：从i 位置开始，窗⼝内所有元素的和小于 target (那么当窗⼝内元素之和第⼀次⼤于等于⽬标值的时候，就是 i 位置开始，满⾜条件的最小长度)。
做法：将右端元素划⼊窗⼝中，统计出此时窗⼝内元素的和：
(1) 如果窗⼝内元素之和⼤于等于target ：更新结果，并且 left++ 将左端元素划出去的同时继续判断是否满⾜条件并更新结果（因为左端元素可能很小，划出去之后依旧满足条件）
(2) 如果窗⼝内元素之和不满足条件： right++ ，另下⼀个元素进入窗口。

细节/技巧问题：

(1) 本题更新结果是在判断成立后更新
(2) 判断，根据判断结果是否出窗口，是循环过程

代码实现：

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

时间复杂度：虽然代码是两层循环，但是我们的 left 指针和 right 指针都是不回退的，两者最多都往后移动 n 次。因此时间复杂度是O(N) 。

算法原理：

解法1：暴力枚举+哈希(判断字符是否重复)，O(N^2)

解法2：滑动窗口+哈希(判断字符是否重复)，O(N)。让滑动窗口满足：窗口内所有元素都是不重复的。通过在草稿纸上进行模拟，我们不难发现规律：

本题使用滑动窗口的流程是：

细节/技巧问题：

(1) 本题可以不用真的使用哈希容器，因为 s 由英文字母、数字、符号和空格组成，所以可以定义一个128大小的数组模拟哈希，就可以找到该字符的映射位置。
(2) 更新结果也是在每次判断结束后更新。

代码实现：

class Solution 
{
public:int lengthOfLongestSubstring(string s) {int hash[128] = {0}; // 用数组模拟哈希，判断字符是否重复出现int left = 0, right = 0, n = s.size();int ret = 0;while(right < n){hash[s[right]]++; // 进窗口while(hash[s[right]] > 1) // 判断字符是否重复出现hash[s[left++]]--; // 出窗口ret = max(ret, right - left + 1); // 更新结果right++;}return ret;}
};

下面是我一开始写的错误代码，以示警告：

class Solution
{
public:int lengthOfLongestSubstring(string s){int n = s.size();unordered_set<char> hash;int left = 0, right = 0;int len = 0;while (right < n){while (hash.count(s[right]) == 0)hash.insert(s[right++]); // 进窗口len = max(len, right - left - 1);while (right < n && s[left] != s[right])hash.erase(s[left++]); // 判断且出窗口left++;right++;}return len;}
};

对比：
正确的代码是每次发现一个重复字符，就会找到那个对应的字符出窗口，而错误的代码把两个重复字符之间的全部字符都出窗口了(包括重复字符)，最后只能通过部分示例。

算法原理：

这道题如果我们按照题目的意思直接翻转0，后续操作会十分麻烦，因为下一次还要把0变回1。所以正难则反，可以把题意转化成：找出最长子数组，其中0的个数不超过 K 个。这样就间接找出了连续 1 的最大个数。

所以可以使用滑动窗口。先在草稿纸上进行模拟：

本题使用滑动窗口的流程是：

代码实现：

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

我一开始写的错误代码，以示警告：

class Solution
{
public:int longestOnes(vector<int>& nums, int k){int left = 0, right = 0, n = nums.size();int zero = 0; // 统计0的个数int ret = 0;while (right < n){if (nums[right] == 0) zero++;while (zero > k){ret = max(ret, right - left);if (nums[left++] == 0) zero--;}right++;}return ret == 0 ? n : ret;}
};

错误代码最大的问题就是没有在判断结束后更新结果，而是边判断边更新结果，这就会导致一些特殊情况，比如[0,0,0,0,0]，k = 0的输出是5。在判断结束之后，窗口改变了再更新结果。

算法原理：

这道题如果我们直接按照题目每次删除最左或最右边的数，会很复杂。所以正难则反，可以把题目转化为：找出最长子数组的长度，使得所有元素的和等于 sum - x，其中sum是全部数据的和，最后的结果用整个数组的长度 - 最长子数组的长度。所以这又回到了我们第一题的思路。

使用滑动窗口，本题的流程是：

细节/技巧问题：

(1) 当 sum - x < 0 时，即 x > sum，就不存在最小操作数，直接返回 -1。
(2) 只有窗口内的所有元素的和等于 sum - x 时，才更新结果。
(3) 最后返回结果时，别忘记进行判断。

代码实现：

class Solution 
{
public:int minOperations(vector<int>& nums, int x) {// 整个数组的和int sum = 0;for(auto e : nums) sum += e;int left = 0, right = 0, n = nums.size();int len = -1, tmp = 0;int target = sum - x;// 细节问题if(target < 0) return -1;while(right < n){tmp += nums[right]; // 进窗口while(tmp > target) // 判断tmp -= nums[left++]; // 出窗口if(tmp == target) // 更新结果len = max(len, right - left + 1);right++;}if(len == -1) return -1;else return n - len;}
};

算法原理：

把这道题"小作文"般的题干转化成：找出一个最长子数组的长度，子数组中不超过两种类型的水果。

涉及到一段连续区间，所以考虑滑动窗口思想：

(1) 初始化哈希表hash来统计窗⼝内⽔果的种类和数量；
(2) 初始化变量：左右指针 left = 0，right = 0，记录结果的变量 ret = 0；
(3) 当right⼩于数组⼤⼩的时候，⼀直执⾏下列循环：
(a) 将当前⽔果放⼊哈希表中；
(b) 判断当前⽔果进来后，哈希表的⼤⼩：
如果超过2：
将左侧元素滑出窗⼝，并且在哈希表中将该元素的频次减⼀；
如果这个元素的频次减⼀之后变成了0，就把该元素从哈希表中删除；
重复上述两个过程，直到哈希表中的⼤⼩不超过2；
(4) 更新结果ret；
right++，让下⼀个元素进⼊窗⼝；
(5) 循环结束后，ret 存的就是最终结果。

代码实现：

class Solution 
{
public:int totalFruit(vector<int>& fruits) {int n = fruits.size();unordered_map<int, int> hash; // 统计窗口内出现多少种水果int left = 0, right = 0, ret = 0;while(right < n){hash[fruits[right]]++; // 进窗口while(hash.size() > 2) // 判断{hash[fruits[left]]--; // 出窗口if(hash[fruits[left]] == 0) hash.erase(fruits[left]); // 当该处水果为0个时，要删除left++;}ret = max(ret, right - left + 1); // 更新结果right++;}return ret;}
};

算法原理：

这道题又是另一种的"滑动窗口"，因为本题的"窗口"的大小是固定的，而前面题目的"窗口"是变化的。

首先先来想清楚如何判断两个长度相同的字符串是否是"异位词"？使用哈希表。把这两个字符串分别扔进两个哈希表，再比较哈希表中每个字符出现的次数，次数相同，则是，否则不是。

所以这道题也是用"滑动窗口 + 哈希表"来解决。先把 p 扔进 hash1 中，再对 s 使用滑动窗口的流程，进窗口，判断，出窗口，判断结束后再更新结果：

代码实现1：

使用数组模拟哈希表。 因为本题只有小写字母，所以可以通过一个整形数组进行映射，在判断"异位词"时最差只要判断26次，也可以通过。

class Solution
{
public:vector<int> findAnagrams(string s, string p){int hash1[26] = { 0 }, hash2[26] = { 0 };int n = s.size(), m = p.size();int left = 0, right = 0;for (auto ch : p) hash1[ch - 'a']++;vector<int> v;while (right < n){hash2[s[right] - 'a']++; // 进窗口if (right - left + 1 > m) // 判断hash2[s[left++] - 'a']--; // 出窗口if (check(hash1, hash2))v.push_back(left); // 更新结果right++;}return v;}// 判断两字符串是否是"异位词"bool check(int* hash1, int* hash2){for (int i = 0; i < 26; i++)if (hash1[i] != hash2[i])return false;return true;}
};

代码实现2：

使用unordered系列容器。其实就是代码1的另一种形式。

class Solution
{
public:vector<int> findAnagrams(string s, string p){int n = s.size(), m = p.size();int left = 0, right = 0;unordered_map<char, int> hash1;for (auto ch : p) hash1[ch]++;vector<int> v;unordered_map<char, int> hash2;while (right < n){hash2[s[right]]++;if (right - left + 1 > m)hash2[s[left++]]--;if (right - left + 1 == m && check(hash1, hash2))v.push_back(left);right++;}return v;}bool check(unordered_map<char, int>& hash1, unordered_map<char, int>& hash2){for (auto& [a, b] : hash2)if (b != hash1[a]) // hash1[a],返回的是key对应的value引用return false;return true;}
};

下面是我写的错误代码，以示警告：

原因是我用 unordered_set 容器只是对字符进行了映射，但是没有对每个字符出现的次数进行统计。

class Solution
{
public:vector<int> findAnagrams(string s, string p){int n = s.size(), m = p.size();int left = 0, right = 0;unordered_set<char> hash1;for (auto ch : p) hash1.insert(ch);unordered_set<char> hash2;vector<int> v;while (right < n){hash2.insert(s[right]);if (right - left + 1 > m)hash2.erase(s[left++]);if (hash2.size() == m && check(hash1, hash2))v.push_back(left);right++;}return v;}bool check(unordered_set<char>& hash1, unordered_set<char>& hash2){for (char ch = 'a'; ch <= 'z'; ch++)if (hash1.count(ch) != hash2.count(ch))return false;return true;}
};

但是这道题还可以进一步优化更新结果的判断条件：利用变量 count 来统计窗口中"有效字符"的个数。目的是判断结果时只需判断一次。
1.什么是"有效字符"。
hash2里与hash1中字符的种类和个数都相同的字符。
2.什么时候维护 count 变量。
(1) 进窗口后：如果进窗口的这个字符在 hash2 里的个数 <= 在 hash1 里的个数，说明是有效字符，count++
(2) 出窗口前：如果出窗口的这个字符在 hash2 里的个数 <= 在 hash1 里的个数，说明是有效字符，count - -
(3) 更新结果时：直接 count == m 即可

代码实现3：

class Solution
{
public:vector<int> findAnagrams(string s, string p){int hash1[26] = { 0 }, hash2[26] = { 0 };int n = s.size(), m = p.size();int left = 0, right = 0;for (auto ch : p) hash1[ch - 'a']++;vector<int> v;int count = 0; // 用来维护hash2中有效字符的个数while (right < n){char in = s[right];//hash2[in]++;// 进窗口+维护countif (++hash2[in - 'a'] <= hash1[in - 'a']) count++;if (right - left + 1 > m) // 判断{char out = s[left++];// 出窗口+维护count// 只有当out字符是有效字符count才减，所以要<=，当为>时说明该字符是多余字符if (hash2[out - 'a']-- <= hash1[out - 'a']) count--;//hash2[out - 'a']--;}if (count == m) v.push_back(left); // 更新结果right++;}return v;}
};

算法原理：

显然，这道题也是使用"滑动窗口+哈希表"。

(1) 先将t 的信息放⼊2 号哈希表中；
(2) 初始化⼀些变量：左右指针： left = 0，right = 0 ；⽬标⼦串的⻓度： len = INT_MAX ；⽬标⼦串的起始位置：begin = -1 😭通过⽬标⼦串的起始位置和⻓度，我们就能找到结果)
(3) 当right ⼩于字符串 s 的⻓度时，⼀直下列循环：
i. 将当前遍历到的元素扔进1 号哈希表中；
ii. 检测当前窗⼝是否满⾜条件：
如果满⾜条件：
判断当前窗⼝是否变⼩。如果变⼩：更新⻓度len ，以及字符串的起始位置 begin；
判断完毕后，将左侧元素滑出窗⼝，顺便更新1 号哈希表；
重复上⾯两个过程，直到窗⼝不满⾜条件；
iii. right++ ，遍历下⼀个元素；
(4) 判断其实位置 begin 是否等于 -1。 如果是，说明没有匹配，返回空串，如果不是，说明匹配，返回 s 中从 begin 位置往后 len ⻓度的字符串。

当然，这道题也可以像前面两题一样优化判断条件：使用 count 变量标记"有效字符的种类"。因为这道题中寻找的子字符串中该字符数量必须不少于 t 中该字符数量，所以不能用有效字符的个数来判断。

代码实现：

class Solution 
{
public:string minWindow(string s, string t){int left = 0, right = 0, kinds = 0;int n = s.size();// 保存t中字符的次数int hash1[128] = {0}, hash2[128] = {0};for(auto ch : t) if(hash1[ch]++ == 0) kinds++; // 统计有效字符有多少种int count = 0, len = INT_MAX, begin = -1; // 子串的起始位置while(right < n){// 进窗口+维护countchar in = s[right];if(++hash2[in] == hash1[in]) count++;// 判断while(count == kinds){if(right - left + 1 < len) // 更新结果{len = right - left + 1;begin = left;}char out = s[left++];if(hash2[out]-- == hash1[out]) count--; // 出窗口}right++;}if(begin == -1) return "";else return s.substr(begin, len);}
};

下面是我用unordered系列容器写的错误代码，以示警告：

class Solution
{
public:string minWindow(string s, string t){int left = 0, right = 0;int n = s.size();// 保存t中字符的次数unordered_map<char, int> hash1;for (auto ch : t) hash1[ch]++;unordered_map<char, int> hash2;string ret, tmp;int len = INT_MAX;while (right < n){// 进窗口char in = s[right];hash2[in]++;// 判断+出窗口while (check(hash1, hash2)){int sz = right - left + 1;tmp = s.substr(left, sz);if (sz <= len) ret = tmp, len = sz; // 更新结果char out = s[left];hash2[out]--;left++;}right++;}return ret;}bool check(unordered_map<char, int>& hash1, unordered_map<char, int>& hash2){for (auto e : hash1)if (hash2[e.first] < e.second)return false;return true;}
};

其实上面的错误代码并没有错，最大的问题就是 check 函数，当测试用例的字符串非常大时， check 函数非常拖后腿，结果如下：