目录
滑动窗口
什么是滑动窗口？
什么时候用滑动窗口？
怎么用滑动窗口？
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);}
};
