題目描述

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

輸入格式

第一行包含整數n。

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

輸出格式

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

數據范圍

1≤n≤100000

輸入樣例：

5
1 2 2 3 5

輸出樣例：

3

解題思路

暴力:

for(int i =0;i<n;++i)for(int j=0;j<=i;++j)if(check(j,i){res = max(res,j-i+1);}

雙指針
slow fast
需要一個哈希表告訴我們當前fast所指向的元素有沒有重復

代碼實現

#include<iostream>
using namespace std;const int N =100010;
int a[N],s[N];
int 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++;}res = max(res, i-j+1);}cout<<res<<endl;return 0;
}