最长连续序列

Leetcode Link: 128. 最长连续序列 - 力扣（LeetCode）

题目

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

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

解法一

思路： 受到题目中”未排序”的启发。

排序后去重，然后看相邻的是不是差 1，然后不断++，但是这样的复杂度不是 $O(n)$

题解：

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums = list(set(nums))
        if len(nums) == 1: # 特例，处理不了，进不去for
            return 1
        nums.sort()
        cnt = 1  # 子序列长度
        res = 0  # 答案
        for i in range(1, len(nums)):
            if nums[i] - nums[i-1] == 1:
                cnt += 1
            else:
                cnt = 1
            res = max(res, cnt)
        return res

为何去重？

避免相等时的报错，如[0,1,2,1] → [0,1,1,2]

解法二

思路 题目要求 $O(n)$ 复杂度。

用哈希表存储每个端点值对应连续区间的长度

• 若数已在哈希表中：跳过不做处理
• 若是新数加入：
  • 取出其左右相邻数已有的连续区间长度 left 和 right
  • 计算当前数的区间长度为：cur_length = left + right + 1
  • 根据 cur_length 更新最大长度 max_length 的值
  • 更新区间两端点的长度值

题解：

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        res = 0 # 最长的长度
        d = dict()
        for num in nums:
            # 新进来哈希表一个数
            if num not in hash_dict:
                # 获取当前数的最左边连续长度,没有的话就更新为0
                left = d.get(num-1,0)
                # 同理获取右边的数
                right = d.get(num+1,0)
                """不用担心左边和右边没有的情况
                因为没有的话就是left或者right0
                并不改变什么
                """
                # 把当前数加入哈希表，代表当前数字出现过
                # 如果不想写这个，可以在最开始将nums变成set，保证来的一定没出现过即可。
                d[num] = 1
                # 更新长度
                length = left+1+right
                res = max(res,length)
                # 更新最左端点的值，如果left=n存在，那么证明当前数的前n个都存在哈希表中
                d[num-left] = length
                # 更新最右端点的值，如果right=n存在，那么证明当前数的后n个都存在哈希表中
                d[num+right] = length
                # 此时 [num-left，num-right] 范围的值都连续存在哈希表中了
                # 即使left或者right=0都不影响结果
        return res

启发和联系