双指针算法

• 两个指针分别指向不同的序列。比如：归并排序的合并过程。
  
• 两个指针指向同一个序列。比如：快速排序的划分过程。
  

原本两个指针是有 种组合，因此时间复杂度是  。
而双指针算法就是运用单调性使得指针只能单向移动，因此总的时间复杂度只有 ，也就是。

题目描述：
给定一个长度为  的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式:
第一行包含整数 。
第二行包含  个整数，表示整数序列。
输出格式:
共  行，每行 个整数，表示所有操作进行完毕后的最终矩阵
输入样例
5
1 2 2 3 5
输出格式:
3

);

    int res = -1;
    for (int i = 0; i < n; i++)
    {
        int cnt = 0;
        int j = i;
        while (j < n)
        {
            if (s[a[j]] >= 1) break;
            s[a[j++]]++;
        }
        res = max(res, j - i);

        // 将计数复原
        for (int k = i; k < j && k < n; k++) s[a[k]]--;
    }

    printf("%d\n", res);
    return 0;
}
上面的代码中定义 s 表示值为 i 的元素出现的次数。 用这个数组相当于用 map 记下来每个元素出现的次数，从而能比较方便的判断出当前序列中是否有重复元素。
另外，需要清楚的知道 i, j 在每次循环跳出的时候指向了什么位置。
我们这里看判断条件 if (s[a[j]] >= 1) break; 可以知道当 a[j] 这个数之前已经出现过的时候，才会跳出。
因此，j这个元素应该已经不能满足序列不重复了，因此从i到j-1表示的是满足题意的序列。
所以，最终的长度是 j - i，而不是 j - i + 1。
<hr/>现在我们已经得到了  时间复杂度的算法，然后我们看一下是否具有单调性。
如果有，则可以使用双指针将其优化到 。
现在我们假设终点为 ，以  为终点，向左找到最长的连续不重复子序列，起点定义为 。
也就是说， 是以  为终点的最长连续不重复子序列。
这里与前面的定义有点不太一样，需要注意一下。
如下图所示。



双指针算法i, j定义的图示

下面考虑单调性：
当  向后移动时， 是否可以沿着一个方向移动？
我们经过考虑，答案是当  向后移动时， 不可能向前移动，这就表示这个方案具有单调性。



当 i 向后移动时，j 不可能向前移动

我们可以使用反证法证明：

  假设  是以  为终点的最长连续不重复子序列。如果当  向后移动时(比如到 )，却向前移动了(比如到 )。
说明了  是以  为终点的最长连续不重复子序列，这就表示 范围内都没有重复元素。
即：以  为终点的最长连续不重复子序列应该是 而不是
（因为 中肯定没有重复元素，而且区间长度还比 长。）
这就与题设的 是以  为终点的最长连续不重复子序列相矛盾。
因此可证明：
当  向后移动时， 不可能向前移动 （可能不动，也可以向后，就是不可能向前）。

当我们证明单调性之后，可以写出使用双指针模板的代码:
#include<iostream>

using namespace std;

const int N = 100010;
int a[N], s[N];

int main()
{
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++) scanf("%d", &a);
   
    int res = -1;
    for (int i = 0, j = 0; i < n; i++)
    {
        s[a]++;
        while (j < i && s[a] > 1) s[a[j++]]--;
        
        res = max(res, i - j + 1);
    }

    printf("%d\n", res);
    return 0;
}
代码中循环内的部分有点绕。
【主要思想】：

  如果可能重复，一定是刚加进来的这个元素重复了，因为在他加进来之前是连续不重复子序列的状态。
所以当进入for循环之后，先把当前元素的个数加上1，然后如果包含了重复元素就后移j指针，直到s[a] == 1为止。

<hr/>以上就是有关双指针算法的所有内容。
想要学习更多有关算法的知识，可以关注我的个人公众号：程序员阿sir