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

[原题链接][https://www.acwing.com/activity/content/11/]

双指针算法

解题思路：

​ 新建一个数组，以每个已知数组的元素大小作为新数组的下标，用来统计每个数字出现的次数，i遍历整个数组，j表示在区间无重复数字的情况下，j向左最远能到达的位置，同时检测这个元素出现的次数，如果这个元素出现的次数大于一，代表当前区间已经有重复数字，需要调整j，使其向右移动，并不断将j途径的元素的记录的数量减一，知道区间无重复数字，同时还要维护一个变量用来记录每次i移动后的区间长度，并且保留这次和上一次之间的较大值。


时间复杂度O(n)


cpp:

#include<iostream>

using namespace std;

const int N = 100010;

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

int main()
{
    cin>>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向右移，缩短区间长度，数字出现次数减一
            j++;
        }
        res = max(res,i-j+1);
    }
    
    cout<<res<<endl;
    
    return 0;
}

author: Trafal

editor: Typora

date: 2020.9.23