双指针

• 第一类：两个序列上的双指针
• 第二类：同一序列的双指针
• 写法：
• 时间复杂度：$o(n)$
• 作用：把$n^2$优化到$o(n)$，优化一重循环
• 做法：先写暴力，看是否具有单调性，再用双指针优化

#include <iostream>

using namespace std;

const int N = 100010;

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

int main()
{
    scanf("%d", &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 (s[a[i]] > 1) 
        {
            s[a[j]] -- ;
            j ++ ;
        }
        res = max(res, i - j + 1);
    }
    printf("%d\n", res);
    return 0;
}