例题
# 概念
其实就是一个队列，当不满足要求时移除队列的元素
# 题目
# LC 3. 无重复字符的最长子串
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
提示
用双指针，窗口中存储不重复字符的子串，i 表示窗口头，j表示窗口尾，用哈希表记录窗口中的字符，当来了一个字符，判断在哈希表中是否出现过
如果未出现过，直接加入到哈希表中，如果出现过，那么不断移动窗口尾指针，直到与窗口头相等为止，移动的过程中不断删除哈希表中的字符。
将尾指针再往前一位，此时从 j 到 i 的子串仍然不存在重复字符
记录出现过的最长窗口长度。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res = 0;
unordered_set<char> u;
int j = 0;
for(int i = 0; i < (int)s.size(); i++){
if(u.find(s[i]) != u.end()){ // 找到
while(s[j] != s[i]){ // 窗口尾不断前移，直到与窗口头一样
u.erase(s[j]); // 删除哈希表中的字符
j++;
}
j++; // 窗口尾再前移一位，保证从j到i是无重复字符的
}else{
u.insert(s[i]);
}
res = max(res, i-j+1);
}
return res;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 76. 最小覆盖子串
https://leetcode-cn.com/problems/minimum-window-substring/
提示
滑动窗口，j是快指针，i是慢指针，当不满足要求时，快指针前移
当满足要求时，慢指针前移，记录出现过的满足要求的最短子串。
class Solution {
public:
string minWindow(string s, string t) {
int n = s.length(), m = t.length();
if(m > n) return ""; // 母串必须不短于子串
int a[128];
int b[128];
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
for(char &c: t) {
b[(int)c]++;
}
int res_len = INT_MAX;
string res = "";
int j = 0, i = 0;
a[(int)s[j]]++;
while(j < n){
if(isok(a, b)){
if(j-i+1 < res_len) {
res = s.substr(i, j-i+1);
res_len = j-i+1;
}
a[(int)s[i]]--;
i++;
}else{
j++;
if(j == n) break;
a[(int)s[j]]++;
}
}
return res;
}
bool isok(int *a, int *b){
for(int i = 0; i < 128; i++){
if(a[i] < b[i]) return false;
}
return true;
}
};
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# 209. 长度最小的子数组
https://leetcode-cn.com/problems/minimum-size-subarray-sum/
提示
方法一：双指针，也是滑动窗口
j 表示快指针，i 表示慢指针
当现在的和大于 target，不断减去左边的节点
提示
方法二：二分
注意：这个需要所有数都是非负数
先求前缀和，然后对每个位置 i ，二分找到第一个大于target的
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int sum = 0, res = INT_MAX;
sum += nums[0];
int i = 0, j = 0;
while(j < (int)nums.size()){
if(sum >= target){
res = min(res, j-i+1);
sum -= nums[i++];
}else{
j++;
if(j == (int)nums.size()) break;
sum += nums[j];
}
}
return res == INT_MAX ? 0 : res;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
还有一种写法，不用增加额外的控制条件
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int sum = 0, res = INT_MAX;
int i = 0, j = 0;
for(int j = 0; j < (int)nums.size(); j++){
sum += nums[j];
while(sum >= target){
res = min(res, j-i+1);
sum -= nums[i++];
}
}
return res == INT_MAX ? 0 : res;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 239. 滑动窗口最大值
https://leetcode-cn.com/problems/sliding-window-maximum/
提示
单调队列，从大到小，队头就是窗口内最大的
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
deque<int> d; // 存索引，原因是需要直到窗口里的元素个数，不足k个需要弹掉
for(int i = 0; i < nums.size(); i++){
// 超过 k 个就要弹掉
if(!d.empty() && d.front() + k-1 < i){
d.pop_front();
}
// 不断弹掉之前窗口里小的，单调队列，从大到小
while(!d.empty() && nums[i] >= nums[d.back()]){
d.pop_back();
}
d.push_back(i);
if(i >= k-1) res.push_back(nums[d.front()]);
}
return res;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 567. 字符串的排列
https://leetcode-cn.com/problems/permutation-in-string/
提示
滑动窗口的长度就是子串的长度
class Solution {
public:
bool checkInclusion(string s1, string s2) {
int n = s1.size(), m = s2.size();
if(n > m) return false;
vector<int>a(26, 0), b(26, 0);
for(int i = 0; i < n; i++){
a[s1[i]-'a']++;
b[s2[i]-'a']++;
}
if(a == b) return true;
for(int j = n, i = 0; j < m; ){
b[s2[j++]-'a']++;
b[s2[i]-'a']--;
i++;
if(a == b) return true;
}
return false;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
编辑 (opens new window)
上次更新: 2025/05/21, 06:42:57