給定一個長度為n的整數序列，請找出最長的不包含重復數字的連續區間，輸出它的長度，
輸入格式
第一行包含整數n，
第二行包含n個整數（均在0~100000范圍內），表示整數序列，
輸出格式
共一行，包含一個整數，表示最長的不包含重復數字的連續子序列的長度，
資料范圍
1≤n≤1000001≤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,i-j+1)
用雙指標演算法，對于每個右端點i，求出最左端點j
for(int i=0,j=0;i<n;i++){ while(j<=i && check(j,i)) j++; res=max(res,i-j+1);
}
具體實作：
import java.util.*; public class Main{ static int n; static final int max=100005; static int a[]=new int[max]; static int s[]=new int[max];//用s陣列記錄當前某個數字的數量 public static void main(String[] args){ Scanner scan=new Scanner(System.in); n=scan.nextInt(); for(int i=0;i<n;i++) a[i]=scan.nextInt(); 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=Math.max(res,i-j+1); } System.out.println(res); } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/107650.html
標籤：其他
上一篇：雙指標演算法模板
下一篇：二級制常用技巧