当前位置: 面试刷题>> 最长连续序列(经典算法150题)


题目描述

给定一个未排序的整数数组 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

解题思路

  1. 使用一个哈希集合(HashSet)来存储数组中的所有元素,以便快速查找某个元素是否存在。
  2. 遍历数组中的每个元素 num,仅当 num - 1 不在哈希集合中时,才开始从 num 出发查找连续序列。这是为了避免重复计算连续序列(即,对于数组中的每个连续序列,我们仅从最小的元素开始计算一次)。
  3. 对于每个满足条件的 num,开始向后查找连续的数,直到某个数不在哈希集合中为止,记录下这段连续序列的长度。
  4. 在遍历过程中,不断更新最长连续序列的长度。

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)。