「滑动窗口算法概述」
文章目录
- 0 滑动窗口的思想
- 1 刷题
- 1.1 最小覆盖子串
- 1.1.1 题解
- 1.1.2 Code
- 1.1.3 结果
- 1.2 字符串排列
- 1.2.1 题解
- 1.2.2 Code
- 1.2.3 结果
- 1.3 找到字符串中所有字母异位词
- 1.3.1 题解
- 1.3.2 Code
- 1.3.3 结果
- 2 总结
0 滑动窗口的思想
思想其实就是之前所说的双指针技巧,滑动窗口其实就是快慢指针的思想,两个指针所组成一个窗口,然后不断向某个方向进行平移。
基本框架和综合框架来自东哥,有兴趣可以关注他的公众号:
int left = 0, right = 0;
while (right < s.size())
{
//增大窗口
window.add(s[right]);
++right;
while (widow needs shrink)
{
//缩小窗口
window.remove(s[left]);
++left;
}
}
现在所要思考的就是什么时候扩大窗口,什么时候缩小窗口。
//滑动窗口算法框架
void SlidingWindow(string s)
{
unordered_map<char, int> window;//Hashmap
//判断key是否存在可以使用count(key)相当于java的containsKey(key)的方法
while (right < s.size())
{
//c是将移入窗口的字符
char c = s[right];
//增大窗口
++right;
//进行窗口内数据的一系列更新
...//根据具体题目
//debug输出
cout << "window: " << left << ", " << right << endl;
//printf("window: [%d, %d]\n", left, right);
//判断左侧窗口是否要收缩
while (window needs shrink)
{
//d是将移出窗口的字符
char d = s[left];
//缩小窗口
++left;
//进行窗口内数据的一系列更新
...//根据具体题目
}
}
}
滑动窗口算法的时间复杂度是 O ( N ) O(N) O(N),虽然有个嵌套的while,但是这两个指针都是在向右边滑动,没有减小,把left和right这之间的区域称之为窗口。这个数组/字符串中的每一个元素都只能进入窗口一次以及移出窗口一次,所以说滑动窗口算法计算其时间复杂度要计算均摊时间复杂度,并且搞清楚区间是左闭右开的!
1 刷题
1.1 最小覆盖子串
1.1.1 题解
子串问题大概率滑动窗口,在字符串s当中使用左右指针的技巧,首先按照框架初始化左右指针为0,然后进行窗口的滑动,首先不断增加right,这样我们的窗口就不断的扩大,直到我们的窗口中的字符串符合要求,也就是包含了T当中所有的字符,这就满足了题目的一个条件,之后,停止扩大窗口,即停止right的++,开始逐步减小窗口,++left,直到这个窗口中的字符串不再包含T当中的字符,同时,每次增加left减小窗口的时候都要进行窗口内容的更新,之后再重复上述步骤,直到窗口穿过字符串s。
思考,什么时候该扩大窗口,什么时候该暂停扩大并且开始缩小窗口,结果是在扩大窗口时更新还是缩小窗口时更新?
扩大窗口:valid还不满足的时候,就是这个窗口还不包含字符串t所要求的的所有字符的时候,我要扩大,先满足这个字符串t的所有要求。
缩小窗口:在满足字符串t所有字符的要求后,进行缩小,因为要找到尽可能短的字符子串。
更新结果:因为要找到尽可能小的子串,所以应该是在缩小窗口的时候去更新,因为缩小窗口的时候,我们窗口里的字符串都是符合条件的,都是包含字符串t的所有字符的。
1.1.2 Code
class Solution {
public:
string minWindow(string s, string t) {
//子串问题大概率滑动窗口
unordered_map<char, int>need, window;
//need就是我们需要凑足的字符有哪些
//window就是记录窗口中有哪些字符
//hashmap类型是char对应int,就是每个字符需要多少个
//window就是去存储每个字符存在多少个
for (char c : t) need[c]++;//把这个t当中每个字符做一个计数
//走框架
int left = 0, right = 0;//左闭右开,初始化
int valid = 0;//存储窗口中满足need条件的字符的个数,valid记录有多少个字符满足了条件,假如ABC,AB满足了valid就是2,还需要+1才能与need.size()相等
//如果valid和need.size()的大小相同,说明该窗口满足条件,满足条件后开始缩小窗口
int start = 0, len = INT_MAX;
//因为要找子串,记录一下子串的长度,所以记录一下目标子串的起始索引和长度
//走框架
while (right < s.size())
{
//c是移入窗口的字符
char c = s[right];
//扩大窗口
++right;
//进行窗口内数据的一系列更新
if (need.count(c))
{
window[c]++;
if (window[c] == need[c])
{
++valid;
}
}
//判断左侧窗口是否要收缩
while (valid == need.size())
{
//在这里更新最小覆盖子串
if (right - left < len)//注意right是开区间,相减就是这个窗口的长度,左闭右开
{
start = left;
len = right - left;
}
//d是将要移出窗口的字符
char d = s[left];
//缩小窗口
++left;
//进行窗口内数据的一系列更新
if (need.count(d))
{
if (window[d] == need[d])//刚好符合要求
{
--valid;//刚好符合要求,移出后肯定不符合要求了,就要valid--
}
--window[d];
}
}
}
//返回最小覆盖子串
return len == INT_MAX ? "" : s.substr(start, len);
}
};
1.1.3 结果
1.2 字符串排列
1.2.1 题解
换句话来说,就是问是否存在s1的排列是s2的子串。代码与上一题基本一致,区别是缩小窗口的时机与之前不一致,left++的时机是窗口大小大于t.size()时,应为排列,所以长度显然是一样的,(right - left >= t.size()
,这是一种定长窗口,因为要找的那个串的大小是一定的,不会像上一题那样扩展的很大或者收缩的很小,此题每次移出窗口只会移出一个字符不会移出多个。所以这个while改成if也是ok的。
1.2.2 Code
class Solution {
public:
bool checkInclusion(string t, string s) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size())
{
char c = s[right];
right++;
//进行窗口内数据的一系列更新
if (need.count(c))
{
window[c]++;
if (window[c] == need[c])
{
valid++;
}
}
//判断左侧窗口是否要收缩
while (right - left >= t.size())
{
//在这里判断是否找到了合法的子串
if (valid == need.size())
{
return true;
}
char d = s[left];
left++;
//进行窗口内数据的一系列更新
if (need.count(d))
{
if (window[d] == need[d])
{
--valid;
}
window[d]--;
}
}
}
return false;
}
};
1.2.3 结果
1.3 找到字符串中所有字母异位词
1.3.1 题解
与上题一样,只不过多了返回索引,在valid == need.size()
的时候,记录一下索引即可。
1.3.2 Code
class Solution {
public:
vector<int> findAnagrams(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
vector<int> res; // 记录结果
while (right < s.size()) {
char c = s[right];
right++;
// 进行窗口内数据的一系列更新
if (need.count(c)) {
window[c]++;
if (window[c] == need[c])
valid++;
}
// 判断左侧窗口是否要收缩
while (right - left >= t.size()) {
// 当窗口符合条件时,把起始索引加入 res
if (valid == need.size())
res.push_back(left);
char d = s[left];
left++;
// 进行窗口内数据的一系列更新
if (need.count(d)) {
if (window[d] == need[d])
valid--;
window[d]--;
}
}
}
return res;
}
};
1.3.3 结果
2 总结
搞清楚滑动窗口的三个问题即可。