目录
模板
应用场景
例题
注意这种写法会出现 Segmentation Fault
模板
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;
// 具体问题的逻辑
}
常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作
应用场景
对于需要双重循环的操作我们把这两个循环的变量设为i，j，那么i，j就是两个指针
例如：for(int i = 0; i < n; i ++ )
for(int j = 0; j < n; j ++ )
其中j需要回溯：因为每一次j都要从一个固定的数（这里为0）开始，无论上一次循环j在什么位置。这样的时间复杂度为O（n^2）
而我们的双指针算法就是要让j不回溯，j直线的从0走到n，那么这样的时间复杂度就是O（2n），即O（n）
综上所述：双指针算法就是通过避免回溯操作将朴素O（n^2）优化到O（2n）即O（n）
例题
799. 最长连续不重复子序列 - AcWing题库
思路：
1.如何判断重复：因为本题数据范围较小，我们可以设置一个s数组来保存每一个值的数量
2.什么时候出现重复：因为我们枚举的是i，所以当元素出现重复的时候，一定是新加入的a[i]与原来的值重复了
3.怎么让j不回溯：在本题中，指针j只能前进不能后退。因为如果j可以后退，说明上一个i对应的指针j构成的区域没有重复的值，说明上一步的j也可以后退一步，这就互相矛盾了，因为我们上一个i对应的i和j构成的区域已经确保是最大的无重复元素的区域了。
4.指针移动带来的变化：如果指针i移动，那么指针i移动后指向的值的数量+1，如果指针j移动，那么j移动前指向的值的数量-1。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int a[N], s[N];
int main()
{
cin >> n;
for(int i = 0; i < n; i ++ ) cin >> a[i];
int res = 0;
for(int i = 0, j = 0; i < n; i ++ )
{
s[a[i]] ++; //指针i指向的值的数量+1
while(s[a[i]] > 1) //只要刚加入的a[i]让序列中存在重复元素
{
s[a[j]] --; //j前进之前指向的值的数量-1
j ++; //j前进
}
res = max(res, i - j + 1);
}
cout << res << endl;
return 0;
}
800. 数组元素的目标和 - AcWing题库
考虑如何让j不回溯：
（1）j从0开始出发：因为两个序列是递增的，所以当指针j停下，即a[i] * b[j] > x的时候，我们移动指针i，这时候可能a[i] * b[j]的值大于x，那么往后所有的a[i] * b[j] 都大于x，这显然是不行的，除非指针j回溯到之前的位置。
（2）j从末尾开始出发：因为枚举的a[i]是逐渐增加的，那么每一次指针j停下的位置永远是往前而不可能回溯到之前的位置的。因为a[i]的值是递增的，那么当a[i] * b[j] > x 的时候，b[j]的值要更小，所以j不需要回溯。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m, x;
int a[N], b[N];
int main()
{
cin >> n >> m >> x;
for(int i = 0; i < n; i ++ ) cin >> a[i];
for(int i = 0; i < m; i ++ ) cin >> b[i];
//j从末尾开始移动
for(int i = 0, j = m - 1; i < n; i ++ )
{
while(a[i] + b[j] > x && j >= 0) j --;
if(a[i] + b[j] == x) cout << i << " " << j << endl;
}
/*j从头开始移动，错误
for(int i = 0, j = 0; i < n; i ++ )
{
while(a[i] + b[j] < x && j < m) j ++;
if(a[i] + b[j] == x) cout << i << " " << j << endl;
else j --;
}
*/
return 0;
}
2816. 判断子序列 - AcWing题库
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], b[N];
int main()
{
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i ++ ) cin >> a[i];
for(int i = 0; i < m; i ++ ) cin >> b[i];
int i, j;
for(i = 0, j = 0; i < n; i ++ ) //i指针指向a,j指针指向b
{
while(a[i] != b[j])
{
if(j == m) //如果i还没有走完j就已经走到头了
{
cout << "No" << endl;
return 0;
}
j ++ ; //不匹配,j前进一位
}
j ++; //匹配,j需要前进一位
}
cout << "Yes" << endl;
return 0;
}
注意这种写法会出现 Segmentation Fault
for(i = 0, j = 0; i < n; i ++ ) //i指针指向a,j指针指向b
{
while(a[i] != b[j])
{
j ++ ; //j前进一位
if(j == m) //如果i还没有走完j就已经走到头了
{
cout << "No" << endl;
return 0;
}
}
j ++; //相等时j需要前进一位
}
解释：
相较于AC的代码，区别仅仅在于当a[i]和a[j]不匹配的时候，我们是先前进j在判断j是否到达了终点
在sg的版本中，如果j++之后j=m了，这时候肯定是不匹配的（b[j]=0），while循环继续，此时j=m+1，if判断无法结束，导致无限while循环（i和j永远不匹配，j一直递增直到越界出现sg）。
而如果先判断if再j++的话，j=m的时候就会直接判断出来。
或者将j==m的判断条件改为j>=m即可。所以说，在这种判断是否越界的问题上，最好使用>=而不是==，因为这种细节很容易忽略，在检查时也会浪费很多时间，并且很多题目都会涉及到。
