滑动窗口
定义
在一个数组中框定一段子数组作为窗口
若想让该窗口元素增加，可以考虑让右边界r++，即窗口从右边吸收数字
若想让该窗口元素减少，可以考虑让左边界l++，即窗口从左边弹出数字
一般解决子数组相关问题
例1/模板
给定一个含有个正整数的数组和一个正整数target
找到累加和target的长度最小的子数组并返回长度，如果不存在符合条件的则返回0
我们可以先固定子数组的左端点，让右端点右移，直到数组和大于target，由于数组所有数都为正整数，因此找到第一个累加和大于target后，后面再加一定也大于target
此时循环判断累加和是否target，若成立则剔出左侧数字，记录子数组长度
然后以该子数组为起点，右端点右移，重复上述操作，寻找等于target的子数组，记录数组长度
时间复杂度：
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
| #include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
int n,tar;
int a[N];
int main()
{
ios
cin >> n >> tar;
for (int i = 1;i<=n;i++){
cin >> a[i];
}
int ans = 0x3f3f3f3f, sum = 0, l = 0;
for (int r = 1;r<=n;r++){
sum+=a[r];
while(sum>=tar){
ans = min(ans,r-l+1);
sum-=a[l++];
}
}
if (ans<=n) cout << ans;
else cout << 0 ;
return 0;
}
|
例2
给定一个字符串，找出不含有重复字符的最长字串长度
即寻找最长无重复字符的窗口
让右边界一直右移，直到遇到重复字符，让左边界移动到max(左边界，重复字符上次位置+1)
因为任何时候窗口情况一定是没有重复数组在内的，若重复字符上次位置比此时左边界小，则若还是移动到重复字符上次位置+1的话，窗口会变长，不保证加长部分会不会又出现重复字符
若右移后无重复字符，可以看作重复字符位置为-1或不存在，用max仍保持原左边界
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
| #include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
string s;
unordered_map<char,int> cnt;
int main()
{
ios
cin >> s;
for (int i = 0;i<s.size();i++) cnt[s[i]]=-1;
int ans = 0;
for (int l = 0, r = 0;r<s.size();r++){
l = max(l,cnt[s[r]]+1);
ans = max(ans,r-l+1);
cnt[s[r]]=r;
}
cout << ans;
return 0;
}
|
例3
给你一个字符串 s 、一个字符串 t 。返回
s 中涵盖 t 所有字符的最小子串。如果
s 中不存在涵盖 t
所有字符的子串，则返回空字符串 "" 。
我们可以逆向以一种”debt”思维解决。遍历要查找的字符，发现一个-1，这样需要查找的字符数都为负数，在查找时，每个字符出现后对应加一，则非
要查找字符将始终为正数，而要查找的字符为负数
先让右边界右移，当debt变为0（窗口包含了足够要查找的字串），开始移动左边界，使字串最小，这时debt大于0的都为不需要查找的字符，故可以左移，直到碰到需要查找的不再移动。
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
| #include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
string s,t;
unordered_map<char,int> cnt;
int main()
{
ios
cin >> s >> t;
if (s.size()<t.size()){
cout << "";
return 0;
}
for (int i = 0;i<t.size();i++) cnt[t[i]]--;
int len = INF, start = 0;
int debt = t.size();
for (int l = 0, r = 0;r<s.size();r++){
if (cnt[s[r]]++<0) debt--;
if(debt==0){
while(cnt[s[l]]>0){
cnt[s[l++]]--;
}
if (r-l+1<len){
len = r-l+1;
start = l;
}
}
}
len == INF ? cout <<"" : cout << s.substr(start,start+len);
return 0;
}
|
总结
关键：找到范围和答案指标之间的单调性关系
求解大流程：求子数组在每个位置开头或结尾情况下的答案
