滑动窗口经典题目
滑动窗口
用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 - x
int 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. 水果成篮
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);
}
};腾讯云开发者
