|
今天我们来学习滑动窗口算法，通过本文，你将彻底学会滑动窗口算法，可以一口气秒杀LeetCode多道算法题！ 滑动窗口算法（Sliding Window）是一种基于数组或字符串的算法技术，它是一种高效的数据处理技术，主要用于处理数组和字符串相关的问题，通过减少循环的嵌套深度来降低算法的时间复杂度。 0. LeetCode相关问题看完本文，你将可以秒杀以下算法题： https:///problems/longest-substring-without-repeating-characters/description/） https:///problems/minimum-window-substring/description/） - · 438. 找到字符串中所有字母异位词 | 中等难度（
https:///problems/find-all-anagrams-in-a-string/description/） https:///problems/permutation-in-string/description/）
1. 滑动窗口关键思路和代码模板1.1 基本思想滑动窗口算法的基本思想是维护一个窗口，这个窗口在数组或字符串上滑动，从而找到满足特定条件的子数组或子字符串。具体来说，算法会设置两个指针，一个指向窗口的左边界（left），另一个指向窗口的右边界（right）。开始时，窗口的大小为0，然后右指针向右移动以扩大窗口，直到满足特定条件为止。一旦满足条件，算法会根据问题的要求更新结果（如记录满足条件的子数组的长度、计算子数组的和等），然后左指针会向右移动以缩小窗口，直到不再满足条件为止。这个过程会一直重复，直到右指针遍历完整个数组或字符串。 1.2 应用场景滑动窗口算法广泛应用于各种字符串和数组问题，包括但不限于： - · 长度最小的子数组问题：例如，找到一个数组中和大于等于某个目标值的长度最小的子数组。
- · 无重复最长子串问题：例如，找到一个字符串中不包含重复字符的最长子串的长度。
- · 乘积小于K的子数组数目问题：例如，给定一个整数数组和一个整数K，找到乘积严格小于K的连续子数组的数目。
- · 字符串匹配问题：例如，在一个较长的字符串中查找一个较短的字符串的所有出现位置。
1.3 代码模板class Solution{
public:
void xxxxx子字符串问题func(string s, string t){
// 前置判断条件
......
int left =0;// 初始化左边界
int right =0;// 初始化右边界
while(right < n)// 右边界到末尾时结束
{
char c = s[right];// 取要加入窗口的字符
right ++;// 窗口右移
// 更新窗口内的信息
......
while(左窗口需要收缩的条件)
{
char d = s[left];
left ++;// 窗口左移
// 更新窗口内的信息
......
}
}
return;
}
};
1.4 套模板，只需要思考以下几个问题（1）什么时候应该扩大窗口？ - 其实这个问题也不用思考，根据模板，最外层循环一直往右扩即可 （2）什么时候应该缩小窗口？ （3）什么时候应该更新答案？ （4）窗口内需要更新什么信息？ 参考：https:///algo/essential-technique/sliding-window-framework/
2. 实战：秒杀算法题2.1 [3. 无重复字符的最长子串] 中等难度2.1.1 套模板前思考问题（1）什么时候应该扩大窗口？ 根据模板，最外层循环一直往右扩即可 （2）什么时候应该缩小窗口？ 当window内的字符计数出现重复（>1）时，这时候应该缩小左边窗口了 （3）什么时候应该更新答案？ 答案是什么？最大长度 什么时候更新？左移完成之后（这时候right - left范围内才没有重复的字符） （4）窗口内需要更新什么信息？ 窗口中每个字符出现的次数 2.1.2 代码实现class Solution{
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
if(n <=1)
{
return n;
}
int left =0;
int right =0;
int max_len =0;
std::unordered_map<char,int> window;
while(right < n)
{
char c = s[right];// 当前字符添加到窗口中
right ++;// 窗口右边界向右移动
window[c]++;// 窗口中字符c的个数加1
while(window[c]>1)// 当窗口中字符c的个数大于1时，左边界向右移动，直到窗口中字符c的个数等于1
{
window[s[left]]--;// 一直移动左边界，直到窗口中字符c的个数等于1
left ++;
}
max_len = std::max(max_len, right - left);
}
return max_len;
}
};
秒了！ 2.2 [76. 最小覆盖子串] 困难难度2.2.1 套模板前思考问题（1）什么时候应该扩大窗口？ 根据模板，最外层循环一直往右扩即可 （2）什么时候应该缩小窗口？ 当window内的字符包含了子串中的所有字符之后，应该尝试缩小左边界了。 （3）什么时候应该更新答案？ 答案是什么？最小子串。可以每次用 substr 取子串，但效率比较低，毕竟每次都生成一个新的字符串，还要拷贝。这里可以记录子串的起始位置以及长度，最后生成一次子串来返回。 什么时候更新？当window内的字符包含了子串中的所有字符之后，这时候就是符合要求的一个子串。再判断下是不是比之前的小，就可以更新结果了。 （4）窗口内需要更新什么信息？ 所需要的字符在窗口中出现的次数。注意：这里不是窗口中字符出现的次数，而是所需要的字符在窗口中出现的次数。if (need.count(c) > 0)这行代码，非常关键。 （可以思考下为什么这里非常关键，如果没有这个条件会怎样？欢迎尝试，评论区留言~） 2.2.2 代码实现class Solution{
public:
string minWindow(string s, string t) {
int n = s.size();
int m = t.size();
if(n < m)
{
return"";
}
std::unordered_map<char,int> window;
std::unordered_map<char,int> need;
for(char c : t)
{
need[c]++;
}
int left =0;
int right =0;
int valid =0;
int start =0;
int len = INT_MAX;
while(right < n)
{
char c = s[right];// 取要加入窗口的字符
right ++;// 窗口右移
if(need.count(c)>0)// 窗口需要字符c
{
window[c]++;// 更新窗口内字符的计数
if(window[c]== need[c])// 此时窗口内字符c的数量达到要求
{
valid ++;// 窗口内达到要求的字符数量
}
}
while(valid == need.size())// need所需要的字符全部包含在窗口内了，这时候缩左边的窗口
{
if(len > right - left)
{
start = left;
len = right - left;
}
char d = s[left];
left ++;// 窗口左移
if(need.count(d)>0)// 窗口需要字符d
{
if(window[d]== need[d])// 窗口内的d的数量不满足要求了
{
valid --;
}
window[d]--;// 更新窗口内字符的计数
}
}
}
return len == INT_MAX ?"": s.substr(start, len);
}
};
困难题都可以秒了！ 2.3 [438. 找到字符串中所有字母异位词] 中等难度2.3.1 套模板前思考问题（1）什么时候应该扩大窗口？ 根据模板，最外层循环一直往右扩即可 （2）什么时候应该缩小窗口？ 当window的长度与所要求子串长度一致时，就可以滑动窗口了。这是一个定长的窗口。 （3）什么时候应该更新答案？ 答案是什么？所有子串的起始索引。 什么时候更新？当window内的字符包含了子串中的所有字符之后，这时候就是符合要求的一个子串。就可以更新结果了。 （4）窗口内需要更新什么信息？ 所需要的字符在窗口中出现的次数。注意：这里不是窗口中字符出现的次数，而是所需要的字符在窗口中出现的次数。if (need.count(c))这行代码，非常关键。 （可以思考下为什么这里非常关键，如果没有这个条件会怎样？欢迎尝试，评论区留言~） 2.3.2 代码实现class Solution{
public:
vector<int> findAnagrams(string s, string p) {
int n = s.size();
int m = p.size();
if(n < m){
return{};
}
std::unordered_map<char,int> need;
for(char c : p)
{
need[c]++;
}
int left =0;
int right = left;
int valid =0;
std::unordered_map<char,int> window;
vector<int> res;
while(right < n)
{
char c = s[right];// 向右扩展
right ++;
if(need.count(c))
{
window[c]++;
if(window[c]== need[c])
{
valid ++;
}
}
while(right - left >= m)// 判断左侧窗口是否需要收缩
{
if(valid == need.size())// 窗口中满足need的字符个数
{
res.push_back(left);
}
char d = s[left];// 左侧收缩的处理
if(need.count(d))
{
if(window[d]== need[d])
{
valid --;
}
window[d]--;
}
left ++;
}
}
return res;
}
};
又秒了！ 2.4 [567. 字符串的排列] 中等难度2.4.1 套模板前思考问题（1）什么时候应该扩大窗口？ 根据模板，最外层循环一直往右扩即可 （2）什么时候应该缩小窗口？ 当window的长度与所要求子串长度一致时，就可以滑动窗口了。这是一个定长的窗口。 （3）什么时候应该更新答案？ 答案是什么？是和否。 什么时候更新？当window内的字符包含了子串中的所有字符之后，这时候就找到符合要求的一个子串。直接返回true。 （4）窗口内需要更新什么信息？ 所需要的字符在窗口中出现的次数。注意：这里不是窗口中字符出现的次数，而是所需要的字符在窗口中出现的次数。if (need.count(c))这行代码，非常关键。 （可以思考下为什么这里非常关键，如果没有这个条件会怎样？欢迎尝试，评论区留言~） 2.4.2 代码实现class Solution{
public:
bool checkInclusion(string s1, string s2) {
int m = s1.size();
int n = s2.size();
if(n < m)
{
returnfalse;
}
std::unordered_map<char,int> need;
for(char c : s1)
{
need[c]++;
}
std::unordered_map<char,int> window;
int left =0;
int right =0;
int valid =0;
while(right < n)
{
char c = s2[right];
right ++;
if(need.count(c))
{
window[c]++;
if(window[c]== need[c])
{
valid ++;
}
}
while(right - left >= m)
{
if(valid == need.size())
{
returntrue;
}
// 收缩左侧窗口
char d = s2[left];
left ++;
if(need.count(d))
{
if(window[d]== need[d])
{
valid --;
}
window[d]--;
}
}
}
returnfalse;
}
};
依然秒了！ 3. 啰嗦一下：滑动窗口算法的注意事项- · 窗口的初始化：通常，窗口的初始大小为0，即两个指针都指向数组的起始位置。
- · 窗口的滑动：窗口的滑动是通过移动左右指针来实现的。右指针通常用于扩大窗口，而左指针则用于缩小窗口。
- · 结果的更新：在滑动窗口的过程中，根据问题的要求更新结果。例如，在寻找长度最小的子数组问题时，每次找到满足条件的子数组时，都会更新记录的最小长度。
- · 边界条件的处理：在处理边界条件时，需要特别注意。例如，当右指针遍历到数组的末尾时，算法的执行就完成了。
如果觉得本文对你有帮助，麻烦点个赞和关注呗 ~~~
- · 大家好，我是 同学小张，持续学习C++进阶、OpenGL、WebGL知识和AI大模型应用实战案例
|
