Medium

题目描述

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

示例 3：

输入：nums = [1,0,1,2]
输出：3

提示：

  • 0 <= nums.length <= 10⁵
  • -10⁹ <= nums[i] <= 10⁹

解题思路

这道题要求在 O(n) 时间内找到最长连续序列，有三种主要解法：

方法一：哈希表（推荐） 使用哈希表存储所有数字，然后对每个数字，只有当它是序列起点时（即 num-1 不存在）才开始向右扩展。这样每个数字最多被访问两次，保证了 O(n) 复杂度。

方法二：排序后遍历 先排序后去重，然后遍历数组统计连续序列长度。时间复杂度 O(n log n)，不满足题目要求但思路简单。

方法三：并查集 将相邻数字进行合并，最后统计最大连通分量。实现复杂，时间复杂度接近 O(n)。

哈希表方法最优：通过识别序列起点避免重复计算，既保证了 O(n) 时间复杂度，又实现简洁。关键在于理解"只从序列起点开始扩展"这一优化思想。

代码实现

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        int maxLength = 0;
        
        for (int num : numSet) {
            // 只有当num是序列的起点时才开始计算
            if (numSet.find(num - 1) == numSet.end()) {
                int currentNum = num;
                int currentLength = 1;
                
                // 向右扩展序列
                while (numSet.find(currentNum + 1) != numSet.end()) {
                    currentNum++;
                    currentLength++;
                }
                
                maxLength = max(maxLength, currentLength);
            }
        }
        
        return maxLength;
    }
};

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums)
        max_length = 0
        
        for num in num_set:
            # 只有当num是序列的起点时才开始计算
            if num - 1 not in num_set:
                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

public class Solution {
    public int LongestConsecutive(int[] nums) {
        HashSet<int> numSet = new HashSet<int>(nums);
        int maxLength = 0;
        
        foreach (int num in numSet) {
            // 只有当num是序列的起点时才开始计算
            if (!numSet.Contains(num - 1)) {
                int currentNum = num;
                int currentLength = 1;
                
                // 向右扩展序列
                while (numSet.Contains(currentNum + 1)) {
                    currentNum++;
                    currentLength++;
                }
                
                maxLength = Math.Max(maxLength, currentLength);
            }
        }
        
        return maxLength;
    }
}

var longestConsecutive = function(nums) {
    const numSet = new Set(nums);
    let maxLength = 0;
    
    for (const num of numSet) {
        // 只有当num是序列的起点时才开始计算
        if (!numSet.has(num - 1)) {
            let currentNum = num;
            let currentLength = 1;
            
            // 向右扩展序列
            while (numSet.has(currentNum + 1)) {
                currentNum++;
                currentLength++;
            }
            
            maxLength = Math.max(maxLength, currentLength);
        }
    }
    
    return maxLength;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度哈希表方法
时间复杂度O(n)
空间复杂度O(n)

时间复杂度分析：

  • 构建哈希表：O(n)
  • 遍历哈希表：O(n)，每个数字最多被访问两次（一次作为起点检查，一次在序列扩展中）
  • 总体：O(n)

空间复杂度分析：

  • 哈希表存储所有数字：O(n)

相关题目