最长连续不重复子序列

Original Link

思想：

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

代码：

代码语言：javascript复制

#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;
}

指针

0 人点赞