Longest Consecutive Sequence
ID
128
Data Type
Hashmap / Hashset
Difficulty
Medium
Tags
Completed Date
May 13, 2024
Preference
🤔 Thought-provoking
题解
哈希表
针对每一个
map
中不存在的数 n
,插入进去都做 2 件事情。第一件事,先查看 n - 1
和 n + 1
是否都存在于 map
中,如果都存在,代表存在连续的序列,那么就更新 left
,right
边界。那么 n
对应的这个小的子连续序列长度为 sum = left + right + 1
。第二件事就是更新 left
和 right
左右边界对应的 length = sum
。![notion image](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2Fa52c2013-6d15-4168-8946-4b51c817fd35%2F91db59a4-eb51-4f91-91ca-010f707a5a9c%2FUntitled.png?table=block&id=1c908d4e-acee-462d-ac0f-3ac3f6f377ca&t=1c908d4e-acee-462d-ac0f-3ac3f6f377ca&width=336&cache=v2)
并查集
利用每个数在
nums
中的下标,把下标和下标进行 union()
,具体做法是看前一个数 nums[i]-1
和后一个数 nums[i]+1
在 map
中是否存在,如果存在就 union()
,最终输出整个并查集中包含最多元素的那个集合的元素总数。