双指针

题目

求一段序列中最长的不重复子列

代码

#include<iostream>
using namespace std;
const int N = 1e5 + 10;

//q是原数组，s用来记录区间内元素的数量，注意这两个N不是一个意思
//第一个是数组的长度，第二个是数组元素的范围
int q[N], s[N];
int n;
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> q[i];
    int res = 0;
    //维护一个区间
    for(int i = 0, j = 0; i < n; i++)
    {
        s[q[i]]++;//向右扩展区间右端点
        //当扩展完区间右端点之后，有可能这个元素q[i]会有重复，下面这个while循环就是用来去除重复
        //去重只有一个办法，就是收缩区间左端点，同时收缩时要保证j是小于i的
        while(j < i && s[q[i]]>1) s[q[j++]] --;//区间数量减一，之后区间断点右移
        //完成上述扩展和收缩之后，该区间是一个满足要求的区间，记录一下长度
        res = max(res, i - j + 1);
    }
    cout << res << endl;

    return 0;
}