实现思路
具体的实现思路如下:
1、定义两个指针 left 和 right,初始值均为 0。
2、定义一个哈希表 map,用于存储每个数字出现的最后位置。
3、当 right 小于序列长度时,执行以下操作:
a. 如果当前数字 nums[right] 在 map 中出现过,并且其最后位置大于等于 left,
说明当前的数字在 left 和 right 区间内出现了重复,
需要更新 left 的值为 map.get(nums[right])+1。
b. 将当前数字和位置存入 map 中。
c. 更新 maxLen 的值为当前 left 和 right 区间的长度和 maxLen 中的最大值。
d. 将 right 的值加 1。
4、输出 maxLen 的值,即为最长不重复连续区间的长度。
时间复杂度 O(n)
空间复杂度 O(n)
Java 代码
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = scanner.nextInt();
}
int left = 0, right = 0, maxLen = 0;
Map<Integer, Integer> map = new HashMap<>();
while (right < n) {
if (map.containsKey(nums[right]) && map.get(nums[right]) >= left) {
left = map.get(nums[right]) + 1;
}
map.put(nums[right], right);
maxLen = Math.max(maxLen, right - left + 1);
right++;
}
System.out.println(maxLen);
}
}