XTY的小站
记录技术笔记和技术博客

128. Longest Consecutive Sequence

22 Jun 2024

128. Longest Consecutive Sequence (Medium) 最长连续序列

题干

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [100,4,200,1,3,2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1] Output: 9

Constraints:

解题思路

独立思考解法

  1. 对数组进行去重，然后排序
  2. 循环数组，找到最大长度值（注意重叠问题）

答案

我的答案

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        seen = set()
        nums[:] = [x for x in nums if not (x in seen or seen.add(x))]
        nums.sort()

        max_len = 0
        cur_len = 0
        for i in range(len(nums)):
            if i == 0 or nums[i] == nums[i-1] + 1:
                cur_len += 1
            else:
                cur_len = 1
            max_len = max(max_len, cur_len)
        return max_len