最長連續不重複子序列_(雙指針)

給定一個長度為n的整數序列，請找出最長的不包含重複數字的連續區間，輸出它的長度。

輸入格式

第一行包含整數n。第二行包含n個整數（均在0~100000範圍内），表示整數序列。

輸出格式

共一行，包含一個整數，表示最長的不包含重複數字的連續子序列的長度。

資料範圍

1≤n≤100000

輸入樣例：

5

1 2 2 3 5

輸出樣例：

3

這個題的題意是要求出一個數組中最長的且連續不重複的子序列。如果暴力的話會是一個O(n^2)的複雜度。

可以用雙指針來做，首先一個指針 i 來表示右端點，指針 j 來表示左端點，當指針 i 向右移動時，指針 j 隻能向右移動或者不移動，這樣就有了單調性，就可以用雙指針來做。因為這個題的資料範圍，是以可以開一個數組來記錄每一個數字出現了幾次，如果資料範圍特别大的話，可以用pair，map來做。

i 指針從左到右移動，然後 j 也是從左到右，如果aa[ i ]出現過 j 指針就向右移動一位，同時這個數出現次數減 1，然後求序列的長度取max

#include<iostream>
#include<algorithm>
using namespace std;
int aa[123456];
int bb[123456];

int main()
{
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>aa[i];
    for(int i=1,j=1;i<=n;i++)
    {
        bb[aa[i]]++;
        while(j<i&&bb[aa[i]]>1) bb[aa[j++]]--;//這個需要寫成while，不能寫成if
        ans=max(ans,i-j+1);
    }
    cout<<ans<<endl; 
    return 0;
}