一、问题分析
滑动窗口的算法技巧的思路非常简单,就是维护一个窗口,不断滑动,然后更新答案。该算法的大致逻辑如下:
int left = 0, right = 0;
while (left < right && right < s.size()) {
// 增大窗口
window.add(s[right]);
right++;
while (window needs shrink) {
// 缩小窗口
window.remove(s[left]);
left++;
}
}
这个算法技巧的时间复杂度是 O(N),比字符串暴力算法要高效得多。
真正麻烦的不是算法的思路,而是各种细节问题。比如说如何向窗口中添加新元素,如何缩小窗口,在窗口滑动的哪个阶段更新结果。即便明白了这些细节,也容易出 bug,找 bug 还不知道怎么找。
二、模板
总结了滑动窗口类算法题的统一模板。
/* 滑动窗口算法框架 */
void slidingWindow(string s) {
// 用合适的数据结构记录窗口中的数据
unordered_map<char, int> window;
int left = 0, right = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
window.add(c)
// 增大窗口
right++;
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/
// 注意在最终的解法代码中不要打印
// 因为 IO 操作很耗时,可能导致超时
cout << left << right;
/********************/
// 判断左侧窗口是否要收缩
while (left < right && window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
window.remove(d)
// 缩小窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}
其中两处 ...
表示的更新窗口数据的地方,到时候你直接往里面填就行了。
而且,这两个 ...
处的操作分别是扩大和缩小窗口的更新操作,你会发现它们操作是完全对称的。
另外,虽然滑动窗口代码框架中有一个嵌套的while
循环,但算法的时间复杂度依然是 O(N)
,其中 N 是输入字符串/数组的长度。
三、例题分析
力扣链接:力扣3.无重复字符的最长子串
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
滑动窗口的思路如下:
- 在字符串 s 中使用双指针中的左右指针技巧,初始化
left = right = 0
,把索引左闭右开区间[left, right)
称为一个「窗口」
; - 先不断地增加
right
指针扩大窗口[left, right)
,直到窗口中的字符串符合要求(有重复字符); - 此时,我们停止增加
right
,转而不断增加left
指针缩小窗口[left, right)
,直到窗口中的字符串不再符合要求(无重复字符)。同时,每次增加left
,我们都要更新一轮结果; - 重复第 2 和第 3 步,直到
right
到达字符串s
的尽头。
这个思路其实也不难,第 2 步相当于在寻找一个「可行解」,然后第 3 步在优化这个「可行解」,最终找到最优解,也就是最短的覆盖子串。左右指针轮流前进,窗口大小增增减减,窗口不断向右滑动,这就是「滑动窗口」这个名字的来历。
套模板的时候,只需要思考以下几个问题:
- 什么时候应该移动 right 扩大窗口?窗口加入字符时,应该更新哪些数据?
- 什么时候窗口应该暂停扩大,开始移动 left 缩小窗口?从窗口移出字符时,应该更新哪些数据?
- 我们要的结果应该在扩大窗口时还是缩小窗口时进行更新?
那么本题完整代码如下:
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<int, char> window;
int left = 0, right = 0;
int result = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 增大窗口
right++;
// 进行窗口内数据的一系列更新
window[c]++;
// 判断左窗口是否要收缩
while (window[c] > 1) {
char d = s[left];
left++;
window[d]--;
}
result = max(result, right - left);
}
return result;
}
};
参考链接
labuladong的算法笔记