维护一个窗口 [left, right]，right 不断向右扩展，满足条件时 left 向右收缩，窗口内的元素始终满足某个条件。
适用场景： 子数组 / 子串问题，求最长 / 最短 / 数量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| int slidingWindow(vector<int>& nums) {
int left = 0, ans = 0;
// 窗口状态变量（计数、求和等）
for (int right = 0; right < nums.size(); right++) {
// 1. 右端点进入窗口，更新窗口状态
while (窗口不满足条件) { // 或 if，看题目
// 2. 左端点移出窗口，更新窗口状态
left++;
}
// 3. 此时窗口是合法的，更新答案
ans = max(ans, right - left + 1);
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int lengthOfLongestSubstring(string s) {
unordered_map<char, int> window;
int left = 0, ans = 0;
for (int right = 0; right < s.size(); right++) {
char c = s[right];
window[c]++;
while (window[c] > 1) { // 出现重复，收缩
char d = s[left];
window[d]--;
left++;
}
ans = max(ans, right - left + 1);
}
return ans;
}
|
找 s 中包含 t 所有字符的最短子串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| string minWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, valid = 0;
int start = 0, minLen = INT_MAX;
for (int right = 0; right < s.size(); right++) {
char c = s[right];
if (need.count(c)) {
window[c]++;
if (window[c] == need[c]) valid++;
}
while (valid == need.size()) { // 满足条件，收缩找最小
if (right - left + 1 < minLen) {
minLen = right - left + 1;
start = left;
}
char d = s[left];
if (need.count(d)) {
if (window[d] == need[d]) valid--;
window[d]--;
}
left++;
}
}
return minLen == INT_MAX ? "" : s.substr(start, minLen);
}
|
注意：有负数时不能用滑动窗口，因为窗口不单调，要用前缀和+哈希。
- 数组元素都是正数（窗口扩展和增大，收缩和减小）
- 求子数组的最长 / 最短 / 数量
- 条件具有单调性：窗口变大条件从满足变不满足（或反过来）
- 有负数（窗口增大和不一定增大）
- 求子序列（不连续）
- 条件不单调
窗口大小固定为 k，滑动遍历：
1
2
3
4
5
6
7
8
9
10
11
12
| // 大小为 k 的子数组最大和
int maxSum(vector<int>& nums, int k) {
int sum = 0;
for (int i = 0; i < k; i++) sum += nums[i]; // 第一个窗口
int ans = sum;
for (int i = k; i < nums.size(); i++) {
sum += nums[i] - nums[i - k]; // 滑一格：加新的，减出去的
ans = max(ans, sum);
}
return ans;
}
|
| 类型 | 代表题 | 思路 |
|---|
| 最长无重复 | LeetCode 3 | 哈希表计数，重复就收缩 |
| 最小覆盖子串 | LeetCode 76 | need + window + valid |
| 字母异位词 | LeetCode 438 | 固定窗口，比较计数 |
| 最长重复字符替换 | LeetCode 424 | 窗口内最多字符数 + k |
| 水果成篮 | LeetCode 904 | 最多两种水果，最长子数组 |
| 和为 s 的最短子数组 | LeetCode 209 | 正整数，收缩求最短 |
| 乘积小于 K 的子数组 | LeetCode 713 | 正数，收缩计数 |
- 初始化 left = 0，答案变量
- 遍历 right 从 0 到 n-1
- 右端点加入窗口，更新状态
- 窗口不合法时，while 循环收缩左端点
- 窗口合法时，更新答案
口诀：右扩左缩，边扩边更，缩完算答