双指针算法的第一道题

简单归纳

1. 先写朴素的写法， 然后看一看i,j之间有没有关系，如果有关系

for(int i = 0, j = 0 ;i < n; i ++ )
    while(j <= i && check(i, j)) 写好判断条件，然后操作

1. 这道题目找寻的是不重复的数字，那么代码每个数字智能出现一次
2. 如果添加a[i]之后有重复的,那么就表示j - i 之间一定有重复的数字，不清楚在哪里
3. 但是我们知道如果要重新计算长度的话，j的位置一定是在第一个重复数字的后面一个
4. 所以我们让s[a[j]]--，让这个重复数字减少一次，从前到后，知道碰到这个重复数字，将次数减少即可

总体而言，关于双指针，缩减时间复杂度的原因在于：

1. 朴素做法是i从前向后遍历一遍，j是每次从0-i, 时间复杂度为1 + 2 + 3 + ··· + n -1: O(n^2);
2. 双指针在于，j每次不向后移动，直向前，所以就是一般1到n 所以时间复杂度为2n，即O(n);
3. 和kmp算法的方式十分类似

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N], s[N];

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++ )    scanf("%d", &a[i]);

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