Java代码
方法一:使用cnt数组
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
int[] cnt = new int[100001];
//读取数组数据
for(int i = 0; i < n; i ++){
a[i] = sc.nextInt();
}
//计算最大区间(使用双指针算法)
int res = 0;
// j表示离i最远的不重复区间的左端点
for(int i = 0, j = 0; i < n; i ++){
cnt[a[i]] ++;
while(cnt[a[i]] > 1){
//区间元素出现重复,从j所在的a[j]元素开始依次向右检查
cnt[a[j]] --;
// j向右移动一位
j ++;
}
//更新区间长度最大值
res = Math.max(res, i - j + 1);
}
System.out.println(res);
}
}
方法二:使用哈希表
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
Map<Integer,Integer> map = new HashMap<>();
int n = sc.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i ++){
a[i] = sc.nextInt();
}
int res = 0;
for(int i = 0, j = 0; i < n; i ++){
if(map.containsKey(a[i])){
//注意:不使用max可能会使得j向左回退,进而出现重复元素
//为了保证j一直向右走,需要将更新后的j与当前的j取一个max进而保证j向右走
j = Math.max(j, map.get(a[i]) + 1);
}
map.put(a[i], i);
res = Math.max(res, i - j + 1);
}
System.out.println(res);
}
}
核心代码解读:
if (map.containsKey(a[i])) {
// 如果当前数字在哈希表中已经存在,更新左端点
j = Math.max(j, map.get(a[i]) + 1);
}
// 将当前数字放入哈希表
map.put(a[i], i);
这段代码的目的是维护一个滑动窗口,该窗口包含不包含重复元素的连续区间。让我来解释这段代码的具体作用:
if (map.containsKey(a[i])) 检查当前数字 a[i] 是否已经在哈希表 map 中存在。如果存在,表示当前区间中已经有一个与 a[i] 相等的元素,即出现了重复元素。
如果存在重复元素,就需要更新左端点 j。这里使用了 j = Math.max(j, map.get(a[i]) + 1) 来更新左端点。具体的含义是,将左端点 j 更新为 map.get(a[i]) + 1,其中 map.get(a[i]) 表示 a[i] 最近一次出现的位置的索引。通过加 1,我们将左端点 j 移动到当前重复元素的下一个位置,以确保窗口内不包含重复元素。
接下来,map.put(a[i], i) 用于将当前数字 a[i] 放入哈希表 map 中,以便记录它的最新位置。这个操作确保了哈希表中存储的位置信息是最新的,以便在下一次遇到重复元素时能够正确更新左端点 j。
总结一下,这段代码的逻辑是,当遇到重复元素时,通过更新左端点 j 来保持滑动窗口内不包含重复元素,然后将当前数字的最新位置存储在哈希表中,以便在下一次遇到相同元素时能够正确地更新左端点。这样,代码能够有效地找到最长不包含重复元素的连续区间的长度。