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 即是左边的连续区间长度，）
- 最终返回最大值。
文章原创，如果觉得写得好，欢迎关注。微信公众号《书所集录》同步更新，同样欢迎关注。
网友评论