之前在用golang二刷代码随想录的时候,遇到209.长度最小的子数组竟然没想到应该用滑动窗口解题!怒而猛刷,并结合各个博客和视频总结滑动窗口题型和模板如下
参考资料:
【精心总结滑动窗口代码模板, 直接搞定80道Leetcode算法题】
【两分钟搞懂滑动窗口算法,致敬3b1b】
【labuladong算法笔记】
再次强调,主要是体会滑动窗口的核心思想,模板只是辅助。
文章目录
- 滑动窗口的使用场景
- 滑动窗口的核心思想
- 使用思路(寻找最长)
- 使用思路(寻找最短)
- 模板
- 典型题型推荐
- 209. 长度最小的子数组
- 3. 无重复字符的最长子串
- set
- map
- 使用数组优化哈希表
- 438. 找到字符串中所有字母异位词
- 数组优化
- 76. 最小覆盖子串
滑动窗口的使用场景
- 很多题目都是找到所谓的子串、子数组、序列等等
- 有一些要求:最长、最小、重复等等
- 条件上的要求满足:串联、覆盖、有无重复、结算结果、出现次数、同时包含XX
一旦出现以上关键词,我们就应该考虑是否能考虑滑动窗口进行解答。
总而言之我认为,它往往是求一个连续的子序列,然后这个子序列要满足某种条件,这种题滑动窗口肯定是可以做的。
滑动窗口的核心思想
滑动窗口一般有几个核心组件:
- 左右指针构成一个窗口
一般是首先移动右指针,然后判断当前窗内是否满足要求,满足要求存储结果,如果不满足要求了,就开始移动左指针,以求重新满足要求,当左右指针重合,可以认为是满足要求的特殊情况,重新开始移动右指针。 - 需要一个容器来存储结果
一般是直接定义一个int整型数,在活动窗口中如果满足要求,将结果存储到容器中。
当右指针都到达末尾的时候,即整个流程结束
使用思路(寻找最长)
核心:左右双指针(L, R)在起始点,R向右逐位滑动
每次滑动过程中:
if : 窗口内元素满足条件,R向右扩大窗口,并更新最优结果
if : 窗口内元素不满足条件,L向右缩小窗口
流程结束:R指针到达结尾,整个流程结束
使用思路(寻找最短)
核心:左右双指针(L, R)在起始点,R向右逐位滑动
每次滑动过程中:
if : 窗口内元素满足条件,L向右缩小窗口,并更新最优结果
if : 窗口内元素不满足条件,R向右扩大窗口
流程结束:R指针到达结尾,整个流程结束
模板
两种情况在代码实现中最大的区别就是:内循环中,一个是result不满足要求;一个是当result满足要求!
最长(大)模板
初始化left, right, result, bestResult
某些时候可能需要合适的容器来承载result和bestResult
个人觉得最常用的就是哈希(包括数组、map、set)
while (右指针没有到结尾) {
窗口扩大,加入right对应元素,更新当前result
while/if (result不满足要求) {
窗口缩小,移除left对应元素,left右移
}
更新最优结果bestResult
right++
}
返回bestResult;
这里while/if的区别主要在于如何移动指针,是逐步缩小窗口,还是直接开始新的窗口更新。
最短(小)模板
初始化left, right, result, bestResult
某些时候可能需要合适的容器来承载result和bestResult
个人觉得最常用的就是哈希(包括数组、map、set)
while (右指针没有到结尾) {
窗口被扩大,加入right对应元素,更新当前result
while/if (result满足要求) {
窗口缩小,移除left对应元素,left右移
}
更新最优结果bestResult
right++
}
返回bestResult;
典型题型推荐
以下为最经典的题型:来自代码随想录和LeeCode hot100
- 209. 长度最小的子数组
- 3. 无重复字符的最长子串
- 438. 找到字符串中所有字母异位词
- 76. 最小覆盖子串
209. 长度最小的子数组
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int right = 0, left = 0;
int curSum = 0;
int bestResult = INT_MAX; // 使用INT_MAX来表示无效的大数,方便之后取最小值
while (right < nums.size()) {
curSum += nums[right]; // 扩展窗口右边界
while (curSum >= target) {
bestResult = min(bestResult, right - left + 1); // 更新最短长度
curSum -= nums[left]; // 缩小窗口
left++; // 正确的是left增加
}
right++; // 继续向右扩展窗口
}
return bestResult == INT_MAX ? 0 : bestResult; // 如果没有更新过bestResult,返回0
}
};
3. 无重复字符的最长子串
本题最核心的就是选一个容器来装字符:
set
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> set; // 用于存储窗口中的字符
int left = 0, right = 0; // 双指针,表示当前的滑动窗口[left, right)
int bestResult = 0; // 最长无重复字符的子串长度
while (right < s.length()) {
char rChar = s[right]; // 右指针对应的字符
// 如果字符已经存在于set中,移动左指针直到移除重复字符
while (set.find(rChar) != set.end()) {
set.erase(s[left]);
left++;
}
// 添加新字符到set中,更新结果,移动右指针
set.insert(rChar);
bestResult = max(bestResult, right - left + 1);
right++;
}
return bestResult;
}
};
map
第一反应是使用unordered_map,我们可以在map中key为出现的字符,value为该字符的下标,方便左边的更新,下边的数组优化方案也是一样的道理,所以并这类题并不需要循环
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> map; // 字符到其最近出现位置的映射
int left = 0, right = 0; // 双指针,表示当前的滑动窗口[left, right)
int result = 0; // 当前窗口的长度
int bestResult = 0; // 最长无重复字符的子串长度
while (right < s.length()) {
char rChar = s[right]; // 右指针对应的字符
if (map.find(rChar) != map.end()) {
// 如果字符已经存在,则可能需要移动左指针
left = max(left, map[rChar] + 1);
}
map[rChar] = right; // 更新或添加字符的最新索引
result = right - left + 1; // 更新当前窗口的长度
bestResult = max(bestResult, result); // 更新最长子串的长度
right++; // 移动右指针
}
return bestResult;
}
};
使用数组优化哈希表
int lengthOfLongestSubstring(string s) {
vector<int> index(256, -1); // ASCII 字符集,所有元素初始化为 -1
int left = 0, right = 0;
int bestResult = 0;
while (right < s.length()) {
char rChar = s[right];
// 如果当前字符已出现过且索引大于等于左指针,则更新左指针
if (index[rChar] != -1 && index[rChar] >= left)
left = index[rChar] + 1;
// 更新当前字符的索引
index[rChar] = right;
// 计算当前无重复字符子串的长度,并更新最长长度
bestResult = max(bestResult, right - left + 1);
// 移动右指针
right++;
}
return bestResult;
}
438. 找到字符串中所有字母异位词
拿到本题很直观的感觉,我们需要一个容器装p
,记录他出现的字母和次数,然后需要一个容器装我们滑动窗口中的字符,然后这两个容器如果匹配上了,那肯定就是异构词了。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> result;
if (s.size() < p.size()) return result;
unordered_map<char, int> pCount, sCount;
//初始化p的字符频率表
for (char c : p) {
pCount[c]++;
}
int left = 0, right = 0;
int required = p.size();
while (right < s.size()) {
//加入当前右指针
char rChar = s[right];
sCount[rChar]++;
//当窗口大小匹配P长度时进行比较
if (right - left + 1 == required) {
if (sCount == pCount) { //存结果
result.push_back(left);
}
//否则窗口左端向右移动,缩小窗口
sCount[s[left]]--;
if (sCount[s[left]] == 0) {
sCount.erase(s[left]);
}
left++;
}
right++;
}
return result;
}
};
数组优化
- 我们使用固定大小的数组代替哈希表
- 减少不必要的比较
- 我们在之前的实现,每次窗口大小达到
p
长度时,我们都会比较两个哈希表,我们可以只在字符频率匹配时才进行这样的比较,即当插入或删除操作可能改变频率表到匹配状态时才检查。
- 我们在之前的实现,每次窗口大小达到
- 滑动窗口计数
- 维护一个计数器来跟踪已匹配的字符种类数量。例如,当某个字符的期望频率与窗口中的频率相匹配时,增加计数器。如果所有字符都匹配,计数器将等于不同字符的总数。这样可以在不比较整个哈希表(指数组)的情况下,通过检查计数器来判断当前窗口是否为有效的异位词。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> result;
if (s.size() < p.size()) return result;
vector<int> pCount(256, 0), sCount(256, 0);
for (char c : p) {
pCount[c]++;
}
int left = 0, right = 0, count = 0;
int pLength = p.size();
while (right < s.size()) {
// 增加右指针字符
if (pCount[s[right]] > 0 && ++sCount[s[right]] <= pCount[s[right]]) {
count++;
}
// 当窗口大小正确,并且计数匹配
if (right - left + 1 == pLength) {
if (count == pLength) {
result.push_back(left);
}
// 减少左指针字符
if (pCount[s[left]] > 0 && sCount[s[left]]-- <= pCount[s[left]]) {
count--;
}
left++;
}
right++;
}
return result;
}
};
76. 最小覆盖子串
和上一题几乎一样
class Solution {
public:
string minWindow(string s, string t) {
if (s.empty() || t.empty() || s.size() < t.size()) return "";
// 字符计数数组
unordered_map<char, int> need, have;
for (char c : t) {
need[c]++;
}
// required 表示需要涵盖的字符种类数
int required = need.size();
int left = 0, right = 0, formed = 0;
int minLen = INT_MAX, minStart = 0; // 用于记录最小子串的起始位置和长度
while (right < s.length()) {
char c = s[right];
have[c]++;
// 如果当前字符的数量符合需求的数量,增加formed
if (need.count(c) && have[c] == need[c]) {
formed++;
}
// 尝试缩小窗口,直到窗口不再满足条件
while (left <= right && formed == required) {
char temp = s[left];
// 更新最小窗口
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minStart = left;
}
// 移动左指针,更新have数组和formed计数
have[temp]--;
if (need.count(temp) && have[temp] < need[temp]) {
formed--;
}
left++;
}
// 移动右指针
right++;
}
return minLen == INT_MAX ? "" : s.substr(minStart, minLen);
}
};