江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第128题：最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

题目描述

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 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 <= 10^5
  • -10^9 <= nums[i] <= 10^9

解题思路

方法一：哈希表

这道题要求找出数组中最长的连续数字序列，并且要求时间复杂度为O(n)，因此不能使用排序（排序的时间复杂度为O(n log n)）。我们可以使用哈希表来解决这个问题。

关键点：

  • 使用哈希表存储数组中的所有数字，便于O(1)时间内查找
  • 对于每个数字x，检查x+1, x+2, …是否在哈希表中，计算连续序列的长度
  • 为了避免重复计算，只有当x-1不在哈希表中时，才开始计算以x为起点的连续序列长度

具体步骤：

  1. 创建一个哈希表，存储数组中的所有数字
  2. 初始化最长连续序列的长度为0
  3. 遍历数组中的每个数字x：
    • 如果x-1不在哈希表中（说明x是一个连续序列的起点）：
      • 初始化当前连续序列的长度为1
      • 检查x+1, x+2, …是否在哈希表中，更新当前连续序列的长度
      • 更新最长连续序列的长度
  4. 返回最长连续序列的长度

时间复杂度：O(n)，其中n是数组的长度。虽然有嵌套循环，但内层循环最多执行n次，因为每个数字只会被作为连续序列的起点计算一次。 空间复杂度：O(n)，需要使用哈希表存储数组中的所有数字。

方法二：并查集

另一种解决方案是使用并查集。并查集是一种树形的数据结构，用于处理一些不交集的合并及查询问题。

关键点：

  • 使用哈希表存储每个数字及其所在连续序列的端点
  • 当遇到一个新的数字x时，检查x-1和x+1是否已经在哈希表中
  • 如果x-1或x+1在哈希表中，将x与相邻的连续序列合并

具体步骤：

  1. 创建一个哈希表，用于存储每个数字及其所在连续序列的端点
  2. 遍历数组中的每个数字x：
    • 如果x已经在哈希表中，跳过
    • 初始化left = x, right = x
    • 如果x-1在哈希表中，更新left = 哈希表[x-1]
    • 如果x+1在哈希表中，更新right = 哈希表[x+1]
    • 更新哈希表[x] = right，哈希表[left] = right，哈希表[right] = left
    • 更新最长连续序列的长度
  3. 返回最长连续序列的长度

时间复杂度：O(n)，其中n是数组的长度。每个数字只会被处理一次。 空间复杂度：O(n)，需要使用哈希表存储数组中的所有数字。

图解思路

哈希表方法分析表

以示例1为例：nums = [100,4,200,1,3,2]

数字 是否为连续序列起点 当前连续序列长度 最长连续序列长度 说明
100 是（99不在哈希表中） 1 1 只有100一个数字
4 是（3不在哈希表中） 1 1 只有4一个数字
200 是（199不在哈希表中） 1 1 只有200一个数字
1 是（0不在哈希表中） 4 4 连续序列：1,2,3,4
3 否（2在哈希表中） - 4 不是连续序列起点，跳过
2 否（1在哈希表中） - 4 不是连续序列起点，跳过

连续序列查找过程表

起点 查找过程 连续序列 长度
100 检查101（不存在） [100] 1
4 检查5（不存在） [4] 1
200 检查201（不存在） [200] 1
1 检查2（存在），检查3（存在），检查4（存在），检查5（不存在） [1,2,3,4] 4

代码实现

C# 实现

public class Solution {
    public int LongestConsecutive(int[] nums) {
        // 创建哈希集合，存储数组中的所有数字
        HashSet<int> numSet = new HashSet<int>(nums);
        
        int longestStreak = 0;
        
        // 遍历数组中的每个数字
        foreach (int num in numSet) {
            // 如果num-1不在哈希集合中，说明num是一个连续序列的起点
            if (!numSet.Contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                
                // 检查num+1, num+2, ...是否在哈希集合中
                while (numSet.Contains(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }
                
                // 更新最长连续序列的长度
                longestStreak = Math.Max(longestStreak, currentStreak);
            }
        }
        
        return longestStreak;
    }
}

Python 实现

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        # 创建哈希集合，存储数组中的所有数字
        num_set = set(nums)
        
        longest_streak = 0
        
        # 遍历数组中的每个数字
        for num in num_set:
            # 如果num-1不在哈希集合中，说明num是一个连续序列的起点
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1
                
                # 检查num+1, num+2, ...是否在哈希集合中
                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1
                
                # 更新最长连续序列的长度
                longest_streak = max(longest_streak, current_streak)
        
        return longest_streak

C++ 实现

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        // 创建哈希集合，存储数组中的所有数字
        unordered_set<int> numSet(nums.begin(), nums.end());
        
        int longestStreak = 0;
        
        // 遍历数组中的每个数字
        for (int num : numSet) {
            // 如果num-1不在哈希集合中，说明num是一个连续序列的起点
            if (numSet.find(num - 1) == numSet.end()) {
                int currentNum = num;
                int currentStreak = 1;
                
                // 检查num+1, num+2, ...是否在哈希集合中
                while (numSet.find(currentNum + 1) != numSet.end()) {
                    currentNum++;
                    currentStreak++;
                }
                
                // 更新最长连续序列的长度
                longestStreak = max(longestStreak, currentStreak);
            }
        }
        
        return longestStreak;
    }
};

执行结果

C# 实现

  • 执行用时：124 ms
  • 内存消耗：58.2 MB

Python 实现

  • 执行用时：148 ms
  • 内存消耗：30.8 MB

C++ 实现

  • 执行用时：56 ms
  • 内存消耗：30.9 MB

性能对比

语言 执行用时 内存消耗 特点
C# 124 ms 58.2 MB 执行速度适中，内存消耗较高
Python 148 ms 30.8 MB 执行速度较慢，内存消耗适中
C++ 56 ms 30.9 MB 执行速度最快，内存消耗适中

代码亮点

  1. 🎯 使用哈希表实现O(1)时间复杂度的查找，满足题目要求的O(n)时间复杂度
  2. 💡 通过判断num-1是否存在，避免重复计算连续序列的长度
  3. 🔍 使用while循环高效地查找连续序列的长度
  4. 🎨 代码结构简洁，逻辑清晰易懂

常见错误分析

  1. 🚫 使用排序算法，导致时间复杂度为O(n log n)，不满足题目要求
  2. 🚫 没有去重处理，导致重复元素影响结果
  3. 🚫 没有正确处理空数组的情况
  4. 🚫 对于每个数字都计算连续序列的长度，导致重复计算，时间复杂度增加

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
哈希表 O(n) O(n) 实现简单，思路清晰 需要额外空间存储所有数字
并查集 O(n) O(n) 可以处理动态添加数字的情况 实现复杂，不直观
排序 O(n log n) O(1) 实现简单，不需要额外空间 不满足题目要求的O(n)时间复杂度

相关题目