双指针
有两个指针,i,j;这两个指针的作用是不一样的
i指针用于计算[j,i]区间中元素出现的个数
j指针的目的是去除[j,i]区间中第一个重复的元素;但是为了去除第一个重复的元素,需要把第一个重复元素前面的数都去除
只有当区间中出现了重复的元素,j指针才开始动,只为了去除
S[n] 数组相当于一个计数器,计算区间中元素出现的次数;
模板
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;
// 具体问题的逻辑
}
至于为什么代码中没有写 j < i;
因为j指针是为了去除第一个重复的元素,而此时i指针在第二个重复元素的位置,所以j 肯定是小于 i的;
Java代码
import java.util.Scanner;
public class Main{
private static int N = 100010;
private static int res;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] a = new int[N];
int[] s = new int[N]; //s数组用来计算[j,i]区间中元素出现的次数
for(int i = 0; i < n; i++) a[i] = in.nextInt();
for(int i = 0, j = 0; i < n; i++){
s[a[i]]++; //i指针开始计数
while(s[a[i]] > 1){ //说明区间[j,i]中出现了重复的元素,j指针开始动,去除第一个重复的元素
s[a[j]]--;
j++; //j指针向前走,每走一步,区间中就会去除一个元素;
}
res = Math.max(res,i - j + 1);
}
System.out.print(res);
}
}