题目描述
blablabla
样例
blablabla
算法1
blablabla
时间复杂度分析:blablabla
C++ 代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
int arr[]=new int[n];
for (int i = 0; i < n; i++) {
arr[i]=scanner.nextInt();
}
System.out.println(find(arr,n));
}
private static int find(int[] arr, int n) {
int res=0;
int s[]=new int[100010];
for (int i = 0,j=0; i <n ; i++) {
s[arr[i]]++;
while (j<i&&s[arr[i]]>1) {s[arr[j]]--;j++;}
res=Math.max(res,i-j+1);
}
return res;
}
}
算法2
blablabla
时间复杂度分析:blablabla
C++ 代码
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
int arr[]=new int[n];
for (int i = 0; i < n; i++) {
arr[i]=scanner.nextInt();
}
System.out.println(find(arr,n));
}
private static int find(int[] arr, int n) {
int pre=-1;
int max=0;
Map<Integer,Integer> map=new HashMap<>();
for (int i = 0; i < n; i++) {
if( map.get(arr[i])!=null){
int index=map.get(arr[i]);
pre = Math.max(pre, index);
}
max=Math.max(max,i-pre);
map.put(arr[i],i);
}
return max;
}
}