双指针算法

原理

双指针算法应用非常广泛，而它能够拿出来作为一种效率较高的算法是因为它和普通的暴力搜索相比，为组合项固定了一些顺序，直接排除了一些组合选项。其思路就是，每次两个指针里面，一个指针负责循环遍历，另一个指针负责检查条件，配合。

常见问题分类：

(1) 对于一个序列，用两个指针维护一段区间 (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

算法实现模板

for (int i = 0, j = 0; i < n; i ++ ) { while (j < i && check(i, j)) j ++ ; // 具体问题的逻辑 }

其中check函数如何选择是值得思考的。

---

---

$例题1维护一段区间$

给定一个长度为n的整数序列，请找出最长的不包含重复数字的连续子序列，输出它的长度。

输入格式

第一行包含整数n。

第二行包含n个整数（均在0~100000范围内），表示整数序列。

输出格式

共一行，包含一个整数，表示最长的不包含重复数字的连续子序列的长度。

数据范围

1≤n≤1000001≤n≤100000

输入样例：

5 1 2 2 3 5

输出样例：

3

题解

这道题目的 check 函数时采用了哈希函数来记录每个元素的计数值来判断当前维护的区间内是否有重复元素

/* *双指针算法能够效率高的原因是因为跟暴力搜索相比，省去了j在i前面的组合情况 *一直都是i在前，j在后，i负责遍历，j负责后期check配合。 */ #include <iostream> #include <unordered_map> const int N = 100000 + 10; using namespace std; int main() { int n; cin >> n; int a[n]; unordered_map<int, int> s; for(int i = 0; i < n; i++) { scanf("%d", &a[i]); } int res = 0; //双指针算法，i在前面，作为负责的节点，j在后面跟随，满足条件才前进 for(int i = 0, j = 0; i < n; i++) { s[a[i]]++; while(j < i && s[a[i]] > 1) s[a[j++]]--; //如果此时有重复数字了 应该将j与i之间的数都去掉，相应的计数有需要挨个去掉 //否则，具体问题的逻辑，此题是计算i j 夹的元素数目 res = max(res, i - j + 1); } cout << res << endl; return 0; }

---

---

$例题2两个数组求和$

给定两个升序排序的有序数组A和B，以及一个目标值x。数组下标从0开始。 请你求出满足A[i] + B[j] = x的数对(i, j)。

数据保证有唯一解。

输入格式

第一行包含三个整数n，m，x，分别表示A的长度，B的长度以及目标值x。

第二行包含n个整数，表示数组A。

第三行包含m个整数，表示数组B。

输出格式

共一行，包含两个整数 i 和 j。

数据范围

数组长度不超过100000。 同一数组内元素各不相同。 1≤数组元素≤1091≤数组元素≤109

输入样例：

4 5 6 1 2 4 7 3 4 6 8 9

输出样例：

1 1

题解

这道题是求两个数组的和与一个给定值匹配，这样的话就是一个指针管一个数组，并且是一首一尾的方式进行，其中 i 指针可以在一个数组中遍历，而另一个 j 则是根据条件来选择前进。 本题的 check 函数是相对好写的

#include <iostream> using namespace std; const int N = 100000 + 10; int main() { int n, m, x; cin >> n >> m >> x; int a[n],b[m]; for(int i = 0; i < n; i++) scanf("%d", &a[i]); for(int j = 0; j < m; j++) scanf("%d", &b[j]); //这里的双指针选取要一个从低点一个从高点 for(int i = 0, j = m - 1; i < n; i++) { while(j > 0 && a[i] + b[j] > x) j--; if(j >= 0 && a[i] + b[j] == x) cout << i <<" "<< j << endl; } return 0; }

总结

双指针算法应用的太广了，这类题目可以在leetcode上找一找，再做几道题练练手。