当前位置：首页 > article >正文

欢乐力扣：最长连续序列

article 2025/2/27 8:50:48

文章目录

1、题目描述
2、思路1
- - 代码

1、题目描述

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

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

在这里插入图片描述

2、思路1

这里我参考题解，讲解的很明白。大致思路是：为了降低遍历的次数，首先判断x-1是否在集合中，若在，则此次遍历可以跳过。因为以x-1为起点的累加绝对比x为起点的序列长。其余情况则可以不断累加遍历，动态更新序列长度。

代码

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        ans = 0 
        st = set(nums)
        for x in st:
            # 核心思想：
            # 若x-1在集合中，则说明以x-1为起点的绝对比以x为起点长！
            # 因此可以不予考虑遍历
            if x - 1 in st:
                continue 
            # 若当前x已经是起点，则不断累加统计长度。
            y = x + 1
            while y in st:
                y += 1
            # 更新ans:y-x即为长度。
            ans = max(ans, y-x)
        return ans