LeetCode | 最长连续序列
404 字
2 分钟
LeetCode | 最长连续序列
分类：哈希表 / 数组
题目
给定一个未排序的整数数组 nums，找出数字连续的最长序列长度。
这个连续序列不要求在原数组里连续出现。
示例：
输入：nums = [100, 4, 200, 1, 3, 2]输出：4原因：最长连续序列是 [1, 2, 3, 4]讲解
暴力做法是：把每个数字都当作起点，然后不断查找 x + 1、x + 2、x + 3 是否存在。这样会重复计算很多次。
优化的关键是：只从连续序列的起点开始数。通过判断x-1在不在集合内来确定x是不是起点。
为了快速判断某个数字是否存在，先把数组转成集合：
st = set(nums)后面还有一个剪枝：
if ans * 2 >= m: break这里 m 是去重后的数字个数。如果当前已经找到的连续序列长度 ans 至少占了一半，那么答案不可能再变得更大。
复杂度
- 暴力做法：
- 时间复杂度：
O(n^2) - 空间复杂度：
O(n)
- 时间复杂度：
- 哈希集合优化：
- 时间复杂度：
O(n) - 空间复杂度：
O(n)
- 时间复杂度：
代码
源码
from typing import List
class Solution: def longestConsecutive(self, nums: List[int]) -> int: st = set(nums) m = len(st)
ans = 0 for x in st: if x - 1 in st: continue
y = x + 1 while y in st: y += 1
ans = max(ans, y - x) if ans * 2 >= m: break
return ans测试
from src.python._128_Longest_Consecutive_Sequence import Solution
sol = Solution()
assert sol.longestConsecutive([100, 4, 200, 1, 3, 2]) == 4assert sol.longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]) == 9assert sol.longestConsecutive([]) == 0assert sol.longestConsecutive([1, 1, 1]) == 1
print("PASS")参考资料
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
LeetCode | 最长连续序列
https://leetcode.cn/problems/longest-consecutive-sequence/相关文章智能推荐
1
LeetCode | 两数之和
LeetCodeLeetCode 两数之和题解：使用 Python 字典作为哈希表，在一次遍历中找到目标下标。
2
LeetCode | 接雨水
LeetCodeLeetCode 接雨水题解：理解每个位置的左右挡板，用双指针在线性时间内计算总积水量。
3
LeetCode | 搜索插入位置
LeetCodeLeetCode 搜索插入位置题解：用二分查找在升序数组中找到目标位置或插入位置。
4
LeetCode | 哈希表
LeetCode整理 LeetCode 哈希表题目的核心思路：先建表，再查表。
5
LeetCode | 矩阵置零
LeetCodeLeetCode 矩阵置零题解：使用行列标记数组记录需要清零的位置，再统一修改原矩阵。
随机文章随机推荐
评论区
--
总访问量
--
访客数
音乐
暂未播放
0:000:00
文章
66
分类
16
标签
93
总字数
477,284
运行时长
0 天
最后活动
0 天前
