最长连续序列
难度:
标签:
题目描述
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109
代码结果
运行时间: 90 ms, 内存: 29.5 MB
/*
* 思路：
* 1. 使用哈希集合（HashSet）存储数组中的所有数字，确保查找的时间复杂度为O(1)。
* 2. 通过Java Stream处理数组，并找到最长的连续序列。
*/
import java.util.HashSet;
import java.util.Set;
import java.util.stream.IntStream;
public class LongestConsecutiveSequenceStream {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) {
return 0;
}
Set<Integer> numSet = new HashSet<>();
for (int num : nums) {
numSet.add(num);
}
return numSet.stream()
.filter(num -> !numSet.contains(num - 1)) // 找到连续序列的起点
.mapToInt(num -> {
int currentNum = num;
int currentStreak = 1;
while (numSet.contains(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
return currentStreak;
})
.max()
.orElse(0); // 返回最大值
}
}
解释
方法:
该题解使用了哈希集合来存储所有数组元素，然后遍历数组中的每个数字。对于每个数字，检查其是否可能是连续序列的开始（即检查这个数字的前一个数字是否不在集合中）。如果是序列的开始，则继续检查下一个数字是否存在于集合中，并更新当前序列的长度，直到找不到下一个连续的数字。这样可以确保每个连续序列只被检查一次，从而使算法的时间复杂度为线性。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在遍历数组元素时，需要检查当前数字的前一个数字不在集合中才开始计算序列长度？
▷🦆
算法中使用的哈希集合能否确保在所有情况下都保持O(n)的时间复杂度，包括哈希冲突的场景？
▷🦆
在更新当前连续序列的长度时，为什么不需要检查数字是否重复出现在数组中？
▷