（算法-雙指針）最長連續不重複子序列

（算法-最長連續不重複子序列）

• 題目描述
• 題目分析
• 解決方案

題目描述

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

輸入格式

第一行包含整數 n。

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

輸出格式

共一行，包含一個整數，表示最長的不包含重複的數的連續區間的長度。

資料範圍

1≤n≤105

輸入樣例：

5
1 2 2 3 5
           

輸出樣例：

3
           

題目分析

1.樸素算法：時間複雜度O(n^2)

for(int i=0,i<n;i++)
	for(int j=0;j<n;j++)
		//i确定j的終點
		//滿足check即j與i之間沒有重複元素
		if(check(j,i))
		{
			res = max(res,i-j+1);
		}
           

2.雙指針算法：時間複雜度O(n)

for(int i=0,j=0;i<n;i++){
	//check即j與i之間沒有重複元素
	//!check 是j到i有重複元素
	while(j<=i && !check(j,i))j++;	
	res = max(res,i-j+1);
	
}
           

解決方案

import java.util.Scanner;

public class Main {
	static int N=100010,n;
	static int[] a = new int [N];
	static int[] s = new int [N];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		for(int i=0;i<n;i++) {
			a[i] = sc.nextInt();
		}
		
		int res = 0;
		for(int i=0,j=0;i<n;i++) {
			//s[a[i]]用來記錄j到i之間a[i]這個數字的個數
			//每次i向後移動一位的時候，都将a[i]這個數字的個數加1，
			s[a[i]]++;
			//如果a[i]這個數字的個數大于1了，就說明j到i之間有重複數字了
			//然後将a[j]這個數字的個數減去1，再将j向右移動
			while(s[a[i]]>1) {
				s[a[j]]--;
				j++;
			}
			res = Math.max(res,i-j+1);
		}
		System.out.println(res);
	}
	
}