滑动窗口 算法

滑动窗口算法

适用场景：

求解子串、子数组、子序列等问题

算法核心思想：

利用左右指针，维护一个窗口，不断移动寻找解集。首先不断增加右窗口指针right来扩大窗口，直到窗口符合要求。之后停止right, 增加左窗口指针left来缩小窗口。每次增加left都需要进行更新。

算法模板：

func(XX)
{// 初始化变量int left = 0;int right = 0;int res = INT_MIN; // 题目求最长子串/子数组int cur_val;...// 初始化窗口容器 统计量// vector string// unordered_map<,> m; // hash常用于统计出现次数、是否存在、是否覆盖、是否匹配// int count;// while (right < XX.size()) {cur_val = XX[right];right++;// 更新容器或者统计数据 （添加、增加）while (condition) { //condition 为缩小窗口的条件// 更新res (根据具体场景)// 更新容器或者统计数据 （移除， 减少）left++;}// 更新res (根据具体场景)}// 更新res (根据具体场景)return res;
}

常见的窗口收缩方法：
 

(1) c重复出现时开始收缩窗口window[cur_val]++; // 容器统计出现的次数while (window[cur_val] > 1) { // 收缩条件为 重复出现cur_val = left的值；window[cur_val]--；left++;}(2) 至多（最多）包含问题window[cur_val]++; // 容器统计出现的次数if (window[cur_val] == 1) count++; // 统计不同字符的个数while(count > k) { // 最多包含k个不同字符// 更新res (根据具体场景)cur_val = left的值；window[cur_val]--；if (window[cur_val] == 0) count--;left++;}(3) 重复序列问题cur_str += right的值； // 当前序列不断更新while (当前序列满足要求) {m[cur_str]++；if (m[cur_str] 重复) {// 找到了当前序列的重复项// 更新}     left++; // 缩小cur_str = cur_str[1, right - left]; // 更新为新的序列}（4）长度为 k 的连续子数组cur_sum += cur_val; while ((right - left) == k) { // 子数组长度为k，满足要求，可以缩小了cur_sum = cur_sum - left的值;left++; } (5) 最多可以替换/翻转k个元素，组成连续相同元素序列。if (right的值是目标连续的值)count++;while(left - right - count > k) {// resif (left的值是目标连续的值) count--;left++；}

必学必会算法题：

无重复字符的最长子串
https://leetcode.cn/problems/longest-substring-without-repeating-characters/

至多包含两个不同字符的最长子串
https://leetcode.cn/problems/longest-substring-with-at-most-two-distinct-characters/

重复的DNA序列
https://leetcode.cn/problems/repeated-dna-sequences/

长度最小的子数组
https://leetcode.cn/problems/minimum-size-subarray-sum/

存在重复元素 II
https://leetcode.cn/problems/contains-duplicate-ii/

至多包含 K 个不同字符的最长子串
https://leetcode.cn/problems/longest-substring-with-at-most-k-distinct-characters/

最大连续1的个数 II
https://leetcode.cn/problems/max-consecutive-ones-ii/

子数组最大平均数 I
https://leetcode.cn/problems/maximum-average-subarray-i/