最长连续不重复子序列

原题链接

思想：

• 双指针。
  • 快指针 i 作为某一连续最长不重复区间的右端点，慢指针 j 作为该区间的左端点；
  • 遍历数组 a[i]，用 vis[a[i]] 标记当前区间内该元素出现的次数。
  • 当 vis[a[i]] > 1 时：
    • 说明当前区间存在重复数字，则 j 不断右移，期间执行 vis[a[j]] --，直到 vis[a[i]] == 1 为止；
    • 此时不含重复数字的区间长度即为 i - j + 1，用 res 来维护最长的区间长度。
  • 否则说明当前区间不存在重复数字，i 持续右移。

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 3;

int a[N];
int vis[N];

void solve(){
    int n; cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];
    int res = 0;
    for(int i = 0, j = 0; i < n; i ++){
        vis[a[i]] ++;
        while(vis[a[i]] > 1 && j < i){
            vis[a[j]] --;
            j ++;
        }
        res = max(res, i - j + 1);
    }
    cout << res << endl;
}

int main(){
    solve();
    return 0;
}