跳至主要內容

3.11 滑动窗口

3.11 滑动窗口

滑动窗口解题框架

滑动窗口算法技巧主要用来解决子数组问题，比如让你寻找符合某个条件的最长/最短子数组。

如果用暴力解的话，你需要嵌套 for 循环这样穷举所有子数组，时间复杂度是 O(n^2)：

for (let i = 0; i < nums.length; i++) {
	for (let j = i; j < nums.length; j++) {
		// nums[i, j] 是一个子数组
	}
}

滑动窗口算法技巧的思路也不难，就是维护一个窗口，不断滑动，然后更新答案，该算法的大致逻辑如下：

let left = 0, right = 0;

while (right < nums.size()) {
    // 增大窗口
    window.addLast(nums[right]);
    right++;

    while (window needs shrink) {
        // 缩小窗口
        window.removeFirst(nums[left]);
        left++;
    }
}

基于滑动窗口算法框架写出的代码，时间复杂度是 O(n)，比嵌套 for 循环的暴力解法效率高。

为啥是 O(n)？

肯定有读者要问了，滑动窗口框架不也用了一个嵌套 while 循环？为啥复杂度是 O(n) 呢？

简单说，指针 left, right 不会回退（它们的值只增不减），所以字符串/数组中的每个元素都只会进入窗口一次，然后被移出窗口一次，不会说有某些元素多次进入和离开窗口，所以算法的时间复杂度就和字符串/数组的长度成正比。

反观嵌套 for 循环的暴力解法，那个 j 会回退，所以某些元素会进入和离开窗口多次，所以时间复杂度就是 O(n^2) 了。

下面我总结了一套滑动窗口算法的代码框架，以后遇到相关的问题，只需默写出来如下框架然后改三个地方就行，保证不会出 bug。

// 滑动窗口算法伪码框架
var slidingWindow = function(s) {
    // 用合适的数据结构记录窗口中的数据，根据具体场景变通
    // 比如说，我想记录窗口中元素出现的次数，就用 map
    // 如果我想记录窗口中的元素和，就可以只用一个 int
    var window = ...;

    var left = 0, right = 0;
    while (right < s.length) {
        // c 是将移入窗口的字符
        var c = s[right];
        window.add(c);
        // 增大窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            var d = s[left];
            window.remove(d);
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
};

下面我们就用四道 LeetCode 原题来实践一下这个框架。

最小覆盖子串

相关题目

📌 76. 最小覆盖子串 - LeetCodeopen in new window

💻 题目大意

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"

输出："BANC"

解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"

输出："a"

解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"

输出: ""

解释: t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。

提示：

  • m == s.length
  • n == t.length
  • 1 <= m, n <= 105
  • s 和 t 由英文字母组成

进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

#### 📌 [76. 最小覆盖子串 - LeetCode](https://leetcode.com/problems/minimum-window-substring/)

#### 💻 **题目大意**

给你一个字符串 `s` 、一个字符串 `t` 。返回 `s` 中涵盖 `t` 所有字符的最小子串。如果 `s` 中不存在涵盖 `t` 所有字符的子串，则返回空字符串 `""` 。

- 对于 `t` 中重复字符，我们寻找的子字符串中该字符数量必须不少于 `t` 中该字符数量。
- 如果 `s` 中存在这样的子串，我们保证它是唯一的答案。

**示例 1：**

> 输入：s = "ADOBECODEBANC", t = "ABC"
>
> 输出："BANC"
>
> 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

**示例 2：**

> 输入：s = "a", t = "a"
>
> 输出："a"
>
> 解释：整个字符串 s 是最小覆盖子串。

**示例 3:**

> 输入: s = "a", t = "aa"
>
> 输出: ""
>
> 解释: t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。

**提示：**

- `m == s.length`
- `n == t.length`
- `1 <= m, n <= 105`
- `s` 和 `t` 由英文字母组成

**进阶**：你能设计一个在 `o(m+n)` 时间内解决此问题的算法吗？

如果我们使用暴力解法，代码大概是这样的：

for (let i = 0; i < s.length(); i++) {
    for (let j = i + 1; j < s.length(); j++) {
        if (s[i:j] 包含 t 的所有字母) {
            更新答案
        }
    }
}

思路很直接，但是显然，这个算法的复杂度大于 O(n^2) 了，不好。

滑动窗口算法的思路是这样：

  1. 使用双指针中的左右指针，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」；
  2. 不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 t 中的所有字符）；
  3. 停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 t 中的所有字符了）；同时，每次增加 left，都要更新一轮结果；
  4. 重复第 2 和第 3 步，直到 right 到达字符串 s 的尽头；

第 2 步相当于在寻找一个「可行解」，第 3 步在优化这个「可行解」，最终找到最优解，也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，一伸一缩，不断向右滑动，这就是「滑动窗口」这个名字的来历。

现在我们来看看这个滑动窗口代码框架怎么用：

首先，初始化 window 和 need 两个哈希表，记录窗口中的字符和需要凑齐的字符：

// 记录 window 中的字符出现次数
let window = {};
// 记录所需的字符出现次数
let need = {};
for (let c of t) {
	need[c] = (need[c] || 0) + 1;
}

然后，使用 left 和 right 变量初始化窗口的两端：

let left = 0,
	right = 0,
	valid = 0;
while (right < s.length) {
	// c 是将移入窗口的字符
	let c = s[right];
	// 扩大窗口
	right++;
	// 进行窗口内数据的一系列更新
	...
}

其中 valid 变量表示窗口中满足 need 条件的字符个数，如果 valid 和 need.size 的大小相同，则说明窗口已满足条件，已经完全覆盖了串 t。

现在开始套模板，只需要思考以下几个问题：

  1. 什么时候应该移动 right 扩大窗口？窗口加入字符时，应该更新哪些数据？
  2. 什么时候窗口应该暂停扩大，开始移动 left 缩小窗口？从窗口移出字符时，应该更新哪些数据？
  3. 我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

如果一个字符进入窗口，应该增加 window 计数器；如果一个字符将移出窗口的时候，应该减少 window 计数器；当 valid 满足 need 时应该收缩窗口；应该在收缩窗口的时候更新最终结果。

下面是完整代码：

var minWindow = function (s, t) {
	let need = {},
		window = {};
	for (let c of t) {
		need[c] = (need[c] || 0) + 1;
	}

	let left = 0,
		right = 0,
		valid = 0;
	// 记录最小覆盖子串的起始索引及长度
	let start = 0,
		len = Infinity;
	while (right < s.length) {
		// c 是将移入窗口的字符
		let c = s[right];
		// 扩大窗口
		right++;
		// 进行窗口内数据的一系列更新
		if (need[c]) {
			window[c] = (window[c] || 0) + 1;
			if (window[c] === need[c]) {
				valid++;
			}
		}

		// 判断左侧窗口是否要收缩
		while (valid === Object.keys(need).length) {
			// 在这里更新最小覆盖子串
			if (right - left < len) {
				start = left;
				len = right - left;
			}
			// d 是将移出窗口的字符
			let d = s[left];
			// 缩小窗口
			left++;
			// 进行窗口内数据的一系列更新
			if (need[d]) {
				if (window[d] === need[d]) {
					valid--;
				}
				window[d]--;
			}
		}
	}
	// 返回最小覆盖子串
	return len === Infinity ? '' : s.substring(start, start + len);
};

上面的代码中，当我们发现某个字符在 window 的数量满足了 need 的需要，就要更新 valid，表示有一个字符已经满足要求。而且，两次对窗口内数据的更新操作是完全对称的。

当 valid == need.size() 时，说明 t 中所有字符已经被覆盖，已经得到一个可行的覆盖子串，现在应该开始收缩窗口了，以便得到「最小覆盖子串」。

移动 left 收缩窗口时，窗口内的字符都是可行解，所以应该在收缩窗口的阶段进行最小覆盖子串的更新，以便从可行解中找到长度最短的最终结果。

字符串排列

相关题目

📌 567. 字符串的排列 - LeetCodeopen in new window

💻 题目大意

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

输入：s1 = "ab" s2 = "eidbaooo"

输出：true

解释：s2 包含 s1 的排列之一 ("ba").

示例 2：

输入：s1= "ab" s2 = "eidboaoo"

输出：false

提示：

  • 1 <= s1.length, s2.length <= 10^4
  • s1 和 s2 仅包含小写字母
#### 📌 [567. 字符串的排列 - LeetCode](https://leetcode.com/problems/permutation-in-string/)

#### 💻 **题目大意**

给你两个字符串 `s1` 和 `s2` ，写一个函数来判断 `s2` 是否包含 `s1` 的排列。如果是，返回 `true` ；否则，返回 `false` 。

换句话说，`s1` 的排列之一是 `s2` 的 **子串** 。

**示例 1：**

> 输入：s1 = "ab" s2 = "eidbaooo"
>
> 输出：true
>
> 解释：s2 包含 s1 的排列之一 ("ba").

**示例 2：**

> 输入：s1= "ab" s2 = "eidboaoo"
>
> 输出：false

**提示：**

- `1 <= s1.length, s2.length <= 10^4`
- `s1` 和 `s2` 仅包含小写字母

这种题目，是明显的滑动窗口算法，相当于给你一个 s1 和一个 s2，请问你 s2 中是否存在一个子串，包含 s1 中所有字符且不包含其他字符。

对于这道题的解法代码，基本上和最小覆盖子串一模一样，只需要改变几个地方：

1、本题移动 left 缩小窗口的时机是窗口大小大于 s1.length 时，因为排列的长度应该是一样的。

2、当发现 valid == need.size() 时，就说明窗口中就是一个合法的排列，所以立即返回 true。

至于如何处理窗口的扩大和缩小，和最小覆盖子串完全相同，按照解题框架即可写出这道题的答案：

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function (s1, s2) {
	let window = {},
		need = {};
	for (let i of s1) {
		need[i] = (need[i] || 0) + 1;
	}

	let left = 0,
		right = 0,
		valid = 0;

	while (right < s2.length) {
		let c = s2[right];
		right++;

		// 进行窗口内数据的一系列更新
		if (need[c]) {
			window[c] = (window[c] || 0) + 1;
			if (window[c] == need[c]) {
				valid += 1;
			}
		}

		// 判断左侧窗口是否要收缩
		while (right - left >= s1.length) {
			// 在这里判断是否找到了合法的子串
			if (valid == Object.keys(need).length) {
				return true;
			}

			let d = s2[left];
			left++;

			// 进行窗口内数据的一系列更新
			if (need[d]) {
				if (window[d] == need[d]) {
					valid--;
				}
				window[d]--;
			}
		}
	}

	// 未找到符合条件的子串
	return false;
};

找所有字母异位词

相关题目

📌 438. 找到字符串中所有字母异位词 - LeetCodeopen in new window

💻 题目大意

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1：

输入：s = "cbaebabacd", p = "abc"

输出：[0,6]

解释：起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。

起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2：

输入：s = "abab", p = "ab"

输出：[0,1,2] 解释：起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。

起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。

起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示：

  • 1 <= s.length, p.length <= 10^4
  • s 和 p 仅包含小写字母
#### 📌 [438. 找到字符串中所有字母异位词 - LeetCode](https://leetcode.com/problems/find-all-anagrams-in-a-string/)

#### 💻 **题目大意**

给定两个字符串 `s` 和 `p`，找到 `s` 中所有 `p` 的 **异位词** 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

**异位词** 指由相同字母重排列形成的字符串（包括相同的字符串）。

**示例 1：**

> 输入：s = "cbaebabacd", p = "abc"
>
> 输出：[0,6]
>
> 解释：起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
>
> 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

**示例 2：**

> 输入：s = "abab", p = "ab"
>
> 输出：[0,1,2]
> 解释：起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
>
> 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
>
> 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

**提示：**

- `1 <= s.length, p.length <= 10^4`
- `s` 和 `p` 仅包含小写字母

这道题的解法，基本上和上一题 字符串排列 一模一样，只需要改变返回值，找到一个合法异位词（排列）之后将起始索引加入 res 即可。

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
	let window = {},
		need = {};
	for (let i of p) {
		need[i] = (need[i] || 0) + 1;
	}

	let left = 0,
		right = 0,
		valid = 0,
		// 记录结果
		res = [];

	while (right < s.length) {
		let c = s[right];
		right++;

		// 进行窗口内数据的一系列更新
		if (need[c]) {
			window[c] = (window[c] || 0) + 1;
			if (window[c] == need[c]) {
				valid++;
			}
		}

		// 判断左侧窗口是否要收缩
		if (right - left == p.length) {
			// 当窗口符合条件时，把起始索引加入 res
			if (valid == Object.keys(need).length) {
				res.push(left);
			}

			let d = s[left];
			left++;

			// 进行窗口内数据的一系列更新
			if (need[d]) {
				if (window[d] == need[d]) {
					valid--;
				}
				window[d]--;
			}
		}
	}
	return res;
};

最长无重复子串

相关题目

📌 3. 无重复字符的最长子串 - LeetCodeopen in new window

💻 题目大意

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

子字符串 是字符串中连续的 非空 字符序列。

示例 1：

输入：s = "abcabcbb"

输出：3

解释：因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入：s = "bbbbb"

输出：1

解释：因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入：s = "pwwkew"

输出：3

解释：因为无重复字符的最长子串是 "wke"，所以其长度为 3。

请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

  • 0 <= s.length <= 5 * 10^4
  • s 由英文字母、数字、符号和空格组成
#### 📌 [3. 无重复字符的最长子串 - LeetCode](https://leetcode.com/problems/longest-substring-without-repeating-characters/)

#### 💻 **题目大意**

给定一个字符串 `s` ，请你找出其中不含有重复字符的 **最长子串** 的长度。

**子字符串** 是字符串中连续的 **非空** 字符序列。

**示例 1：**

> 输入：s = "abcabcbb"
>
> 输出：3
>
> 解释：因为无重复字符的最长子串是 "abc"，所以其长度为 3。

**示例 2:**

> 输入：s = "bbbbb"
>
> 输出：1
>
> 解释：因为无重复字符的最长子串是 "b"，所以其长度为 1。

**示例 3:**

> 输入：s = "pwwkew"
>
> 输出：3
>
> 解释：因为无重复字符的最长子串是 "wke"，所以其长度为 3。
>
> 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

**提示：**

- `0 <= s.length <= 5 * 10^4`
- `s` 由英文字母、数字、符号和空格组成

这题变简单了，连 need 和 valid 都不需要，更新窗口内数据只需要简单的更新计数器 window 即可。

当 window[c] 值大于 1 时，说明窗口中存在重复字符，不符合条件，就该移动 left 缩小窗口了。

唯一需要注意的是，在哪里更新结果 res 呢？

这里和之前不一样，要在收缩窗口完成后更新 res，因为窗口收缩的 while 条件是存在重复元素，换句话说收缩完成后一定保证窗口中没有重复。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
	let window = {},
		left = 0,
		right = 0,
		// 记录结果
		res = 0;

	while (right < s.length) {
		let c = s[right];
		right++;
		// 进行窗口内数据的一系列更新
		window[c] = (window[c] || 0) + 1;
		// 判断左侧窗口是否要收缩
		while (window[c] > 1) {
			let d = s[left];
			left++;
			// 进行窗口内数据的一系列更新
			window[d]--;
		}
		// 在这里更新答案
		res = Math.max(res, right - left);
	}

	return res;
};

遇到子数组/子串相关的问题，只要能回答出来以下几个问题，就能运用滑动窗口算法：

  1. 什么时候应该扩大窗口？
  2. 什么时候应该缩小窗口？
  3. 什么时候应该更新答案？

好了，滑动窗口算法模板就讲到这里，希望你能理解其中的思想，记住算法模板并融会贯通。

相关题目

固定长度窗口

题号标题题解标签难度
1343大小为 K 且平均值大于等于阈值的子数组数目open in new window数组 滑动窗口
643子数组最大平均数 Iopen in new window[✓]数组 滑动窗口
1052爱生气的书店老板open in new window数组 滑动窗口
1423可获得的最大点数open in new window数组 前缀和 滑动窗口
1456定长子串中元音的最大数目open in new window[✓]字符串 滑动窗口
567字符串的排列open in new window[✓]哈希表 双指针 字符串 1+
1100长度为 K 的无重复字符子串 🔒open in new window哈希表 字符串 滑动窗口
1151最少交换次数来组合所有的 1 🔒open in new window数组 滑动窗口
1176健身计划评估 🔒open in new window数组 滑动窗口
438找到字符串中所有字母异位词open in new window[✓]哈希表 字符串 滑动窗口
995K 连续位的最小翻转次数open in new window位运算 队列 数组 2+
683K 个关闭的灯泡 🔒open in new window树状数组 线段树 队列 5+
220存在重复元素 IIIopen in new window数组 桶排序 有序集合 2+
239滑动窗口最大值open in new window[✓]队列 数组 滑动窗口 2+
480滑动窗口中位数open in new window数组 哈希表 滑动窗口 1+

不定长度窗口

题号标题题解标签难度
674最长连续递增序列open in new window数组
485最大连续 1 的个数open in new window[✓]数组
487最大连续1的个数 II 🔒open in new window数组 动态规划 滑动窗口
76最小覆盖子串open in new window[✓]哈希表 字符串 滑动窗口
718最长重复子数组open in new window数组 二分查找 动态规划 3+
209长度最小的子数组open in new window[✓]数组 二分查找 前缀和 1+
862和至少为 K 的最短子数组open in new window队列 数组 二分查找 4+
1004最大连续1的个数 IIIopen in new window[✓]数组 二分查找 前缀和 1+
1658将 x 减到 0 的最小操作数open in new window数组 哈希表 二分查找 2+
424替换后的最长重复字符open in new window哈希表 字符串 滑动窗口
3无重复字符的最长子串open in new window[✓]哈希表 字符串 滑动窗口
1695删除子数组的最大得分open in new window数组 哈希表 滑动窗口
1208尽可能使字符串相等open in new window字符串 二分查找 前缀和 1+
1493删掉一个元素以后全为 1 的最长子数组open in new window数组 动态规划 滑动窗口
727最小窗口子序列 🔒open in new window字符串 动态规划 滑动窗口
159至多包含两个不同字符的最长子串 🔒open in new window哈希表 字符串 滑动窗口
340至多包含 K 个不同字符的最长子串 🔒open in new window哈希表 字符串 滑动窗口
795区间子数组个数open in new window数组 双指针
992K 个不同整数的子数组open in new window数组 哈希表 计数 1+
713乘积小于 K 的子数组open in new window数组 二分查找 前缀和 1+
904水果成篮open in new window数组 哈希表 滑动窗口
1358包含所有三种字符的子字符串数目open in new window哈希表 字符串 滑动窗口
467环绕字符串中唯一的子字符串open in new window字符串 动态规划
1438绝对差不超过限制的最长连续子数组open in new window队列 数组 有序集合 3+
Copyright © 2024 2xiao