哈希表法快速求解最长连续序列 | 力扣128题详细解析

❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容，和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣！

• 推荐：数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注
  

• 导航：

  • LeetCode解锁1000题: 打怪升级之旅：每题都包括3-5种算法，以及详细的代码实现，刷题面试跳槽必备
  • 漫画版算法详解：通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读，看一遍就掌握
  • python源码解读：解读python的源代码与调用关系，快速提升代码质量
  • python数据分析可视化：企业实战案例：企业级数据分析案例与可视化，提升数据分析思维和可视化能力
  • 程序员必备的数学知识与应用：全面详细的介绍了工程师都必备的数学知识

期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️

题目描述

给定一个未排序的整数数组 nums，找出数字连续的最长序列的长度。要求时间复杂度在 O(n) 内。

注意：

• 这个序列不需要在原数组中是连续的。

示例：

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度是 4。
1
2
3

方法一：哈希表

解题步骤

1. 使用哈希表存储所有数字，以便快速查找数组中的任意数字是否存在。
2. 遍历数组 nums，对每个元素进行检查：
   • 如果其前一个元素 (num - 1) 不在哈希表中，则这是一个新序列的起点。
3. 从起点开始，递增查找连续的数字，同时更新最长连续序列的长度。
4. 返回找到的最大长度。

Python 示例

def longestConsecutive(nums):
    num_set = set(nums)
    max_length = 0

    for num in num_set:
        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

# 示例使用
nums = [100, 4, 200, 1, 3, 2]
print(longestConsecutive(nums))  # 输出: 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

算法分析

• 时间复杂度：O(n)。尽管看起来有双层循环，但每个数字在内层循环中只访问一次。
• 空间复杂度：O(n)，因为需要存储数组元素的哈希表。

详细步骤说明

1. 构建哈希表：

   • 将所有数字插入哈希表，确保每个数字能被快速查找。
   • 例如，对于输入 [100, 4, 200, 1, 3, 2]，哈希表为 {100, 4, 200, 1, 3, 2}。

2. 查找序列起点：

   • 遍历哈希表中的每个数字，判断是否为序列的起点。
   • 一个数字是序列起点的条件是其前一个数字不在哈希表中。
   • 例如，1 是起点，因为 0 不在哈希表中。

3. 构建序列：

   • 从序列起点开始，逐步查找下一个连续数字，并计算序列长度。
   • 例如，从 1 开始，可以找到 2、3 和 4，最终序列长度为 4。

更多示例

1. 输入：[0, -1, 1, 2, 3]

   • 输出：5
   • 解释：最长连续序列是 [-1, 0, 1, 2, 3]，长度为 5。

2. 输入：[10, 5, 12, 3, 55, 6, 11, 8, 7, 9]

   • 输出：6
   • 解释：最长连续序列是 [5, 6, 7, 8, 9, 10]，长度为 6。

图示与说明

考虑 nums = [100, 4, 200, 1, 3, 2]：

1. 构建哈希表：

   • 哈希表：{100, 4, 200, 1, 3, 2}

2. 查找序列起点：

   初始数组: [100, 4, 200, 1, 3, 2]
   哈希表构建: {100, 4, 200, 1, 3, 2}
   
   从 '1' 开始，因为 '0' 不在集合中，序列可以从 '1' 开始向上构建:
   1 -> 2 -> 3 -> 4
   连续序列长度为 4，是此数组的最长连续序列。
   1
   2
   3
   4
   5
   6

3. 详细步骤说明：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/605147