【题解】最长连续不重复子序列

双指针

• 双指针其核心思想就是将 O(n^2) 的朴素算法优化到 O(n) 。

• s[i] 表示 整数 i 在区间 [j,i] 中出现的次数。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

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

int slove(int l, int r)
{
    int ans = 0;
    //找i,j满足的某种单调性规律，使得两个指针对于每个元素均只遍历一次
    for (int i = 1, j = 1; i <= n; i ++)
    {
        //当i++后表示i指向的元素出现次数增加一次
        s[a[i]] ++;
        //j++表示j指向的元素出现次数减少一次
        while (s[a[i]] > 1) s[a[j]] --, j ++;
        ans = max(ans, i - j + 1);
    }
    return ans;
}

int main()
{
    cin >>n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    
    int ans = slove(1, n);
    cout << ans;
    return 0;
}