128. 最长连续序列

题目

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

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

解题思路

思路：哈希表

本题主要的难点在于算法时间复杂度限定为 O(n) 的方法上。

先假设一般的情况下。可以尝试枚举数组中每个元素 i，以其起点不断尝试匹配 +1，+2 … 是否存在于数组中，这样不断枚举并更新最大的长度。当然，这样会非常消耗时间，因为当你枚举 i 结束时，再次遇到元素值 i+1 时，这里又将重新匹配。（考虑改进）

可以考虑使用集合的方法，先使用集合，将数组去重。这里需要改进的就是重复匹配的情况。

当使用集合的方法时，这里先说明一下，在什么样的情况下才要去开始计算长度，而不需要重复去匹配。如果 i 的前面一个数 i-1 存在于集合当中，那么它在这个时候就需要被跳过。因为它与 i 是可以组成连续序列的，只要在 i-1 的时候计算即可。

那么也就是，当 i 存在前驱数 i-1 的时候，不需要计算，直接跳过。只有当 i 无前驱数时，才可以当成是起始的位置开始计算长度。遍历匹配不断更新最大值即可。（具体代码就不贴了，这里给出大概的思路，可尝试编写）

现在主要介绍本篇幅使用的哈希表的方法。

这里哈希表的键是每个端点，而值则是它对应连续区间的长度。

具体的做法：

• 构建哈希表，遍历数组；
• 如果数已经存在于哈希表中，那么跳过不做处理；
• 如果数是新数的情况下，那么这里新数将需要查找左右相邻数对应的值（也就是左右相邻数字对应的连续区间的长度）。这里与当前数的长度相加就是这个数对应的新区间长度。length = left + 1 + right
• 需要与最大的长度值进行比较，更新最大值
• 同时还需要更新两个端点的区间长度值。

具体的代码实现如下。

代码实现

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        hash_dict = {}

        max_length = 0

        for num in nums:
            # 这里表示新数进来
            # 此时需要查找左右相邻的两个数对应的区间长度
            # 左右两个数的长度 + 自身的长度，就是此时新数对应的区间长度
            if num not in hash_dict:
                # 如果键不在哈希表中，取值 0
                pre_length = hash_dict.get(num - 1, 0)
                next_length = hash_dict.get(num + 1, 0)

                cur_length = pre_length + 1 + next_length
                
                if cur_length > max_length:
                    max_length = cur_length
                
                # 添加新数，同时更新两个端点的值
                # 因为序列是连续的，此时两侧端点对应的区间长度会因为当前数的加入发生改变
                hash_dict[num] = cur_length
                hash_dict[num-pre_length] = cur_length
                hash_dict[num+next_length] = cur_length
        
        return max_length

实现结果

总结

• 本篇幅使用的是哈希表的方法。哈希表的 key 存的是端点，而 value 存储的端点对应的连续区间长度。
• 具体的实现的做法：
  • 构建哈希表，遍历数组
  • 当遇到存在于哈希表的数字，不做处理跳过
  • 当遇到新数时，需要查找左右相邻的数对应的区间长度，与自身长度相加。（左右数字不存在于哈希表中，返回 0），与最大值比较同时更新最大值。
  • 将新数与其对应的区间长度存入哈希表中，同时更新左右两个端点的值。（例如左边数对应的连续区间长度的起始位置，即是 num - pre_length。num 表示当前数，pre_length 即是左边的连续区间长度，）
  • 最终返回最大值。