双指针（尺取）
通过两个（或多个）移动的标记，高效地探索或处理数据结构中的连续部分，以简化问题并加快求解速度，通常称为双指针、尺取或滑动窗口等。
例：单词背诵
给一个单词表以及一个文章，要在文章里找包含单词表中单词最多的前提下最短的一段。
进一步解释：在文章中找到起点第 \(i\)
个单词，终点第 \(j\)
个单词，包含单词表中单词数量最多的\([i,j]\)
区间可能不唯一，找最短的那个区间。
输入 \(n\) 然后 \(n\) 个单词的单词表，接着输入 \(m\) 然后 \(m\) 个单词的文章。
输入
1
2
3
4
5
6
7
8
9
10
| 3
hot
dog
milk
5
hot
dog
dog
milk
hot
|
输出
这道题有“包含最多”和“长度最短”两个要求，而“包含最多”的要求是优先的，这说明要不放弃任何一个包含的单词。
将起点 \(j\) 和终点 \(i\) 设置为双指针， \(i\) 先走。
- \(i\) 走一步：
- 文章第 \(i\)
个单词是否是单词表里的单词
- 目前的 \([j,i]\)
区间包含了这个单词几次
- \(j\) （可能）走多步：
- 文章第 \(j\)
个单词如果不是单词表里的， \(j\)
向前走一步
- 文章第 \(j\)
个单词是单词表里的，且目前 \([j,i]\)
区间包含不止一个， \(j\)
向前走一步
- 文章第 \(j\)
个单词是单词表里的，但目前 \([j,i]\)
区间里只有 1 个，\(j\)
停下，不再尝试往前走
- 现在 \([j,i]\)
包含单词数是否增多，\([j,i]\)长度（
i-j+1）是否更短，更新答案
- 重复执行 1) ~ 3)
关于是否包含、包含几个的问题，我们学过hash和字典树都可以很容易处理了，当然如果你已熟练掌握，那么现在可以用STL的map或unorderd_map。
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
48
49
| #include<cstdio>
#include<algorithm>
#include<map>
#include<string>
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
char a[maxn][21], b[maxm][21];
int n, m;
int main() {
scanf("%d", &n);
std::map<std::string, int> mp;
for(int i = 0; i < n; i ++) {
scanf("%s", a[i]);
mp[a[i]] = 0;
}
scanf("%d", &m);
for(int i = 0; i < m; i ++) {
scanf("%s", b[i]);
}
int tmp_cnt = 0, ans_cnt = 0, ans_len = m;
for(int i = 0, j = 0; i < m; i ++) {
if(mp.count(b[i])) {
mp[b[i]] ++;
if(mp[b[i]] == 1) {
tmp_cnt ++;
}
}
while(j <= i) {
if(mp.count(b[j])) {
if(mp[b[j]] > 1) {
mp[b[j]] --;
} else {
break;
}
}
j ++;
}
if(tmp_cnt >= ans_cnt) {
if(tmp_cnt > ans_cnt || i - j + 1 < ans_len) {
ans_len = i - j + 1;
}
ans_cnt = tmp_cnt;
}
}
printf("%d\n%d\n", ans_cnt, ans_len);
return 0;
}
|
例：挑选钻石
给定 \(N\) 颗钻石的大小和一个整数
\(K\)（\(N
\leq 50,000\), \(0 \leq K \leq
1,000,000,000\)），你的任务是确定可以在两个展示柜中展示的最大钻石数量。如果两颗钻石的大小之差超过
\(K\)，则它们不能放在同一个展示柜中；若大小之差恰好为
\(K\)，则可以放在同一个展示柜中。
分析：如果把 \(N\)
个数排序，那么答案就是找两个不重叠的子串，每个子串最大值与最小值差不超过\(K\)，两个子串长度之和最大的方案。
在排序后，先考虑找一个这样的子串的最大方案怎么找：双指针保持 \(i\) 和 \(j\) 的价值之差不超过 \(K\)，统计最长的一段。
考虑找两个不重叠的：如果对任意划分界限，界限左边找一段最长的，界限右边也找一段最长的，最优方案一定在某一个界限时得到。
需要快速知道确定界限时，左边和右边各自的最优解。
- 从左往右双指针一遍：记录每个位置作为界限，左边的最优解
- 从右往左双指针一遍：记录每个位置作为界限，右边的最优解
- 枚举界限，把左右最优解加起来，找全局最优
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
| #include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<map>
#include<string>
const int maxn = 5e4 + 10;
int n, k, a[maxn], l_max[maxn], r_max[maxn];
int main() {
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i ++) {
scanf("%d", &a[i]);
}
std::sort(a, a + n);
memset(l_max, 0, sizeof(l_max));
memset(r_max, 0, sizeof(r_max));
for(int i = 0, j = 0; i < n; i ++) {
for(;j < i && a[i] - a[j] > k; j ++);
l_max[i] = std::max(i > 0 ? l_max[i - 1] : 0, i - j + 1);
}
for(int i = n - 1, j = n - 1; i >= 0; i --) {
for(;j > i && a[j] - a[i] > k; j --);
r_max[i] = std::max(i < n - 1 ? r_max[i + 1] : 0, j - i + 1);
}
int ans = 0;
for(int i = 0; i < n; i ++) {
ans = std::max(ans, l_max[i] + r_max[i + 1]);
}
printf("%d\n", ans);
return 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
| #include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<map>
#include<string>
const int maxn = 5e4 + 10;
int n, k, a[maxn];
int main() {
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i ++) {
scanf("%d", &a[i]);
}
std::sort(a, a + n);
int ans = 0, l_max = 0;
for(int i = 0, j = 0, r = 0; i < n; i ++) {
for(;j < i && a[i] - a[j] > k; j ++);
l_max = std::max(l_max, i - j + 1);
for(; r < n && i < n - 1 && a[r] - a[i + 1] <= k; r ++);
ans = std::max(ans, r - i - 1 + l_max);
}
printf("%d\n", ans);
return 0;
}
|