题目描述
给定一个未排序的整数数组 nums
,找出其中最长连续元素序列的长度。要求算法的时间复杂度为 O(n),其中 n 是数组 nums
的长度。
示例 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
解题思路
- 使用一个哈希集合(HashSet)来存储数组中的所有元素,以便快速查找某个元素是否存在。
- 遍历数组中的每个元素
num
,仅当num - 1
不在哈希集合中时,才开始从num
出发查找连续序列。这是为了避免重复计算连续序列(即,对于数组中的每个连续序列,我们仅从最小的元素开始计算一次)。 - 对于每个满足条件的
num
,开始向后查找连续的数,直到某个数不在哈希集合中为止,记录下这段连续序列的长度。 - 在遍历过程中,不断更新最长连续序列的长度。
PHP 代码示例
function longestConsecutive($nums) {
if (empty($nums)) {
return 0;
}
$numSet = array_flip($nums); // 使用数组翻转创建哈希集合
$maxLength = 0;
foreach ($nums as $num) {
if (!isset($numSet[$num - 1])) { // 仅当 num-1 不在集合中时开始检查
$currentNum = $num;
$currentLength = 1;
while (isset($numSet[$currentNum + 1])) { // 向后查找连续序列
$currentNum++;
$currentLength++;
}
$maxLength = max($maxLength, $currentLength);
}
}
return $maxLength;
}
Python 代码示例
def longestConsecutive(nums):
if not nums:
return 0
num_set = set(nums)
max_length = 0
for num in nums:
if num - 1 not in num_set: # 仅当 num-1 不在集合中时开始检查
current_num = num
current_length = 1
while current_num + 1 in num_set: # 向后查找连续序列
current_num += 1
current_length += 1
max_length = max(max_length, current_length)
return max_length
JavaScript 代码示例
function longestConsecutive(nums) {
if (nums.length === 0) {
return 0;
}
const numSet = new Set(nums);
let maxLength = 0;
for (let num of nums) {
if (!numSet.has(num - 1)) { // 仅当 num-1 不在集合中时开始检查
let currentNum = num;
let currentLength = 1;
while (numSet.has(currentNum + 1)) { // 向后查找连续序列
currentNum++;
currentLength++;
}
maxLength = Math.max(maxLength, currentLength);
}
}
return maxLength;
}
在以上三种语言的实现中,我们都遵循了相同的逻辑,并且使用了哈希集合来优化查找过程,以确保算法的时间复杂度为 O(n)。