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

本文涉及的产品
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
简介: 哈希表法快速求解最长连续序列 | 力扣128题详细解析

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

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

题目描述

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

注意:

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

示例:

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

方法一:哈希表

解题步骤

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

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

算法分析

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

详细步骤说明

  1. 构建哈希表
  • 将所有数字插入哈希表,确保每个数字能被快速查找。
  • 例如,对于输入 [100, 4, 200, 1, 3, 2],哈希表为 {100, 4, 200, 1, 3, 2}
  1. 查找序列起点
  • 遍历哈希表中的每个数字,判断是否为序列的起点。
  • 一个数字是序列起点的条件是其前一个数字不在哈希表中。
  • 例如,1 是起点,因为 0 不在哈希表中。
  1. 构建序列
  • 从序列起点开始,逐步查找下一个连续数字,并计算序列长度。
  • 例如,从 1 开始,可以找到 234,最终序列长度为 4

更多示例

  1. 输入:[0, -1, 1, 2, 3]
  • 输出:5
  • 解释:最长连续序列是 [-1, 0, 1, 2, 3],长度为 5
  1. 输入:[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}
  1. 查找序列起点
初始数组: [100, 4, 200, 1, 3, 2]
哈希表构建: {100, 4, 200, 1, 3, 2}
从 '1' 开始,因为 '0' 不在集合中,序列可以从 '1' 开始向上构建:
1 -> 2 -> 3 -> 4
连续序列长度为 4,是此数组的最长连续序列。
  1. 详细步骤说明
步骤 当前数字 当前序列 最长序列长度
初始 [100, 4, 200, 1, 3, 2]
构建哈希表 {100, 4, 200, 1, 3, 2}
步骤1 1 [1] 1
步骤2 1 -> 2 [1, 2] 2
步骤3 1 -> 2 -> 3 [1, 2, 3] 3
步骤4 1 -> 2 -> 3 -> 4 [1, 2, 3, 4] 4

🌹🌹如果觉得这篇文对你有帮助的话,记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励,非常感谢 ❥(^_-)

❤️❤️作者知识有限,如有错误,请各位大佬评论区批评指正,不胜感激❥(^_-)

欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
3月前
|
Python
【Leetcode刷题Python】376. 摆动序列
文章提供了解决LeetCode "摆动序列" 问题的Python实现代码,通过遍历整数数组并使用两个变量 down 和 up 来记录正差和负差摆动序列的长度,最终返回最长摆动子序列的长度。
39 0
|
5月前
|
索引
力扣随机一题 6/26 哈希表 数组 思维
力扣随机一题 6/26 哈希表 数组 思维
36 0
|
3月前
|
Python
【Leetcode刷题Python】946. 验证栈序列
LeetCode题目“946. 验证栈序列”的Python解决方案,通过模拟栈的压入和弹出操作来验证给定的两个序列是否能通过合法的栈操作得到。
29 6
|
3月前
|
算法 Python
【Leetcode刷题Python】剑指 Offer 33. 二叉搜索树的后序遍历序列
本文提供了一种Python算法,用以判断给定整数数组是否为某二叉搜索树的后序遍历结果,通过识别根节点并递归验证左右子树的值是否满足二叉搜索树的性质。
22 3
|
3月前
|
Python
【Leetcode刷题Python】105. 从前序与中序遍历序列构造二叉树
LeetCode上105号问题"从前序与中序遍历序列构造二叉树"的Python实现,通过递归方法根据前序和中序遍历序列重建二叉树。
25 3
|
3月前
|
算法 Python
【Leetcode刷题Python】300. 最长递增子序列
LeetCode 300题 "最长递增子序列" 的两种Python解决方案:一种使用动态规划,另一种使用贪心算法结合二分查找。
36 1
|
4月前
|
自然语言处理 算法 搜索推荐
字符串相似度算法完全指南:编辑、令牌与序列三类算法的全面解析与深入分析
在自然语言处理领域,人们经常需要比较字符串,这些字符串可能是单词、句子、段落甚至是整个文档。如何快速判断两个单词或句子是否相似,或者相似度是好还是差。这类似于我们使用手机打错一个词,但手机会建议正确的词来修正它,那么这种如何判断字符串相似度呢?本文将详细介绍这个问题。
272 1
|
3月前
|
算法 Java
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
42 0
|
3月前
|
Python
【Leetcode刷题Python】674. 最长连续递增序列
LeetCode 674题 "最长连续递增序列" 的Python解决方案,使用动态规划算法找出给定整数数组中最长连续递增子序列的长度。
94 0

推荐镜像

更多