一、算法描述
含义
-
双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。
-
另外还可以根据序列进行区分，例如在快排中，双指针指向的是同一个序列，而归并排序中两个指针指向的是两个不同的序列。
怎么用
-
没有必要对概念区分的很清楚，只需要知道怎么使用即可。
-
首先想暴力解法，然后在暴力解法的基础之上，发现性质，进行优化。
-
通过题目来理解什么是双指针吧。
二、题目描述
给定一个长度为 \(n\) 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式
第一行包含整数 \(n\)。
第二行包含 \(n\) 个整数（均在 \(0\) ~ \(10 ^ 5\) 范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围
\(1 ≤ n ≤ 10 ^ 5\)
输入样例：
5
1 2 2 3 5
输出样例：
3
三、题目来源
四、算法思路
-
首先暴力做法就是，枚举左端点 \(l\) ，枚举右端点 \(r\) ，然后枚举区间 \([l, r]\) 判断是否有重复数字，然后更新答案，显然该做法时间复杂度会非常高，所以可以优化一下。
-
如何优化呢？
-
遍历数组 \(a\) 中的每一个元素 \(a[i]\) , 对于每一个\(i\)，找到j使得双指针 \([j, i]\) 维护的是以 \(a[i]\) 结尾的最长连续不重复子序列，长度为 \(i - j + 1\) , 将这一长度与 \(res\) 的较大者更新给\(res\)。
-
对于每一个 \(i\) ，如何确定j的位置：由于 \([j, i - 1]\) 是前一步得到的最长连续不重复子序列，所以如果 \([j, i]\) 中有重复元素，一定是 \(a[i]\)，因此右移 \(j\)直到 \(a[i]\) 不重复为止（由于 \([j, i - 1]\) 已经是前一步的最优解，此时 \(j\) 只可能右移以剔除重复元素 \(a[i]\)，不可能左移增加元素，因此， \(j\) 具有“单调性”、本题可用双指针降低复杂度）。
五、源代码
#include <iostream>
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]];
while (j <= i && s[a[i]] > 1)
{
-- s[a[j]];
++ j;
}
res = max(res, i - j + 1);
}
cout << res << endl;
return 0;
}