滑动窗口经典题目

滑动窗口

什么是滑动窗口？

什么时候用滑动窗口？

怎么用滑动窗口？

209. 长度最小的子数组（滑动窗口的引入）

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

1004. 最大连续1的个数 III

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

904. 水果成篮

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

30. 串联所有单词的子串

76. 最小覆盖子串

滑动窗口

用209. 长度最小的子数组 - 力扣（LeetCode）这一题引入

什么是滑动窗口？

同向双指针，两个指针都不回退时

什么时候用滑动窗口？

当数组有单调性时（可能是数组本身有单调性，也可能是和）

怎么用滑动窗口？

1、初始化：初始化双指针

2、进窗口

3、判断

判断是不是要出窗口

❁ 更新结果（有些是在进窗口时，有些是在出窗口时）

209. 长度最小的子数组（滑动窗口的引入）

题目链接：. - 力扣（LeetCode）

题目要求满足sum >= target，又因为数组内都是正整数，所以sum随着数组的遍历是递增的，有单调性的

有单调性时，我们可以想到：1、双指针 2、二分 3、滑动窗口

有了双指针就可以不用二分，因为双指针很多时候能降低时间复杂度

我们可以设置l指针为窗口的起点，r为窗口的终点

1、如果sum < target,r++

2、如果sum > target,l++

sum跟着上面变

我们会发现l和r是同向移动的，也就是“同向双指针”，滑动窗口的基本特点就是：1、单调性2、同向双指针

滑动窗口怎么用？

1、初始化l和r

2、进窗口

3、判断

判断是否满足出窗口条件

以上环节注意更新结果(该题为sum),可能是在进窗口时改变,也可能是在出窗口时改变

正确性?

利用了单调性(该题为sum),规避了很多不必要的操作

(如sum > target时,我们不需要管r之后的数据了,因为题目要求求"长度最小的",r后面的数据一定满足sum > target,都是len是一直增大的,对于该题来说就是无用功)

时间复杂度:O(N)

虽然有两层循环,但是实际上时间复杂度是2*N,因为r最后结果是到末尾,为N,l最坏结果是也到末尾,也是N

因此时间复杂度不看循环层数，而是看实际操作

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {if (nums.size() == 0)return 0;int l = 0, r = 0;int sum = 0, len = INT_MAX;while (r < nums.size()){sum += nums[r];r++;while (sum >=/*注意有个=*/ target){len = min(len, r - l);sum -= nums[l];l++;}        }return len > nums.size() ? 0 : len;}
};

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

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

❀ 注意标记数组不能是大小为26，因为“s 由英文字母、数字、符号和空格组成”，所以最好开256

❀ 两个指针都是往后走，也就是同向指针 ----> 滑动窗口

class Solution
{
public:int lengthOfLongestSubstring(string s){int len = 0, l = 0, r = 0;int book[256] = { 0 };// 不只有字母while (r < s.size()){// 进窗口 book[s[r]]++;// 判断while (book[s[r]] > 1){// 出窗口book[s[l++]]--;}// 更新数据 len = max(len, r - l + 1);// 下一元素进窗口r++;}return len;}
};

1004. 最大连续1的个数 III

题目链接：. - 力扣（LeetCode）

解题思路：

滑动窗口解法

1、初始化指针

l = 0, r = 0

2、进窗口

1无视，0增加zero计数

3、出窗口

1无视，0减少计数

class Solution {
public:int longestOnes(vector<int>& nums, int k){if (k >= nums.size())return nums.size();int l = 0, r = 0;int len = 0;int zero = 0;// 记录当前范围0的个数while (r < nums.size()){// 进窗口if (!nums[r])zero++;// 判断while (zero > k)/**/{// 出窗口if (!nums[l++])zero--;}len = max(len, r - l + 1/*左闭右闭*/);r++;}return len;}
};

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

题目链接:. - 力扣（LeetCode）

解题思路：

❀ 正难则反，我们可以通过找“和为（数组元素的和 - x ）的最长连续子数组” ，来求得答案

❀ 上面那一步就是《双指针经典题目-CSDN博客》双指针经典题目中的《两数之和》的题目，其实滑动窗口本质上就是双指针，只不过它是同向移动的双指针

❀ 同时我们可以注意一下数据范围：1 <= nums[i] <= 10^4

因此，我们可以知道数据元素都为正数，因此和具有单调性

class Solution {
public:// 正难则反// 找最长的子数组，使得其和为sum - xint minOperations(vector<int>& nums, int x) {int size = nums.size();if (min(nums[size - 1], nums[0]) > x)return -1;// 双指针，都指向数组开头，然后同向移动，找最大长度int l = 0, r = 0;int totalsum = 0;// 整个数组的和for (auto e : nums)totalsum += e;totalsum -= x;// 整个数组的和 - x// 因为数据元素都为正数if (totalsum == 0)return nums.size();else if (totalsum < 0)return -1;int sum = 0;int len = 0;for (r = 0; r < nums.size(); r++){sum += nums[r];while (l < r && sum > totalsum){sum -= nums[l];l++;}if (sum == totalsum){len = max(len, r - l + 1);}}if (!len)return -1;return nums.size() - len;}
};

904. 水果成篮

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

class Solution {
public:int totalFruit(vector<int>& fruits){int hash[100001] = { 0 };int l = 0, r = 0;int ret = 0;int size = 0;for (r = 0; r < fruits.size(); r++){if (hash[fruits[r]] == 0)size++;// 进窗口hash[fruits[r]]++;// 出窗口while (size > 2){hash[fruits[l]]--;if (hash[fruits[l]] == 0)size--;l++;}// 更新结果ret = max(ret, r - l + 1);}cout << ret << endl;return ret;}
};

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

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

如何知道两个字符串是否为异位词？
1、可以给两个字符串排序（时间复杂度高）
2、用两个哈希表分别记录两个子串的各个字母个数

该题解法：滑动窗口 + 哈希表
该题的滑动窗口：右边进入一个数值，左边出一个数值，维持窗口大小不变
用一个count记录有效字符的个数
1、进窗口
如果是有效字符，count++
2、出窗口
更新结果：如果count == p.size()，ans.push_back(l);
出窗口：如果是有效字符，count--

class Solution
{
public:vector<int> findAnagrams(string s, string p) {int hash1[26] = { 0 };int hash2[26] = { 0 };        for (auto e : p)hash1[e - 'a']++;int l = 0, r = 0;vector<int> ans;int count = 0;while (r < s.size()){// 进窗口hash2[s[r] - 'a']++;// 说明是有效字符if (hash2[s[r] - 'a'] <= hash1[s[r] - 'a'])count++;if (r - l + 1 == p.size()){if (count == p.size()){ans.push_back(l);hash2[s[l] - 'a']--;count--;// 移除的一定是有效字符}else// count < p.size(){hash2[s[l] - 'a']--;// 删除的是有效字符if (hash2[s[l] - 'a'] < hash1[s[l] - 'a'])count--;}l++;}r++;}return ans;}
};

30. 串联所有单词的子串

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

解题思路：

将题目想为“在s中找words的异位词”

class Solution
{
public:vector<int> findSubstring(string s, vector<string>& words){// 滑动窗口的次数int size = words[0].size();// 检验字符串的长度int len = words.size() * words[0].size();unordered_map<string, int> mp1;unordered_map<string, int> mp2;vector<int> ans;for (auto e : words)mp1[e]++;// 看是否是串联子串int l = 0, r = words[0].size();int prel = 0;// 看是否构成一个单词int midl = 0, midr = words[0].size();while (size--){// 有效字符串的个数int count = 0;mp2.clear();while (r <=/*注意有一个等于,因为构造字符串是左闭右开，在构造最后一个单词的时候，r要等于s.end()*/ s.size()){// 进窗口 string temp(s.begin() + midl, s.begin() + midr);// string temp = s.substr(l, words[0].size());mp2[temp]++;if (mp2[temp] <= mp1[temp])count++;if (r - l == len){string temp(s.begin() + l, s.begin() + l + words[0].size());mp2[temp]--;if (count == words.size()){ans.push_back(l);count--;}else{if (mp2[temp] < mp1[temp])count--;}l += words[0].size();}r += words[0].size();midr += words[0].size();midl += words[0].size();}l = ++prel;midl = l;r = l + words[0].size();midr = midl + words[0].size();}return ans;}
};

76. 最小覆盖子串

题目链接：. - 力扣（LeetCode）

1、暴力解法：两层循环 + 哈希表
2、优化解法：滑动窗口 + 哈希表

kind:t中字符的种类
count:s中字符的种类(注意！不是个数)

进窗口
如果是t中的字符，并且++hash1[r] == hash2[r]，count++
判断
如果--hash2[l] < hash1[l]，count--
出窗口
如果出的数据不是t中的数据，r不变
如果出的数据是t中的数据，r++

更新结果

class Solution {
public:string minWindow(string s, string t){if (s.size() < t.size())return "";int l = 0, r = 0;int hash1[256] = { 0 };int hash2[256] = { 0 };int kind = 0;for (auto e : t){if (hash1[e]++== 0)kind++;}int count = 0;int len = INT_MAX;int lenl = 0;for (r = 0; r < s.size(); r++){hash2[s[r]]++;if (hash2[s[r]] == hash1[s[r]])count++;while (count == kind){if ((r - l + 1) < len){len = r - l + 1;lenl = l;}if (hash2[s[l]]-- == hash1[s[l]])count--;l++;}}if (len == INT_MAX)return "";return s.substr(lenl, len);}
};