Longest Consecutive Sequence
|Last edited: 2024-5-14
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 中,如果都存在,代表存在连续的序列,那么就更新 leftright 边界。那么 n 对应的这个小的子连续序列长度为 sum = left + right + 1。第二件事就是更新 left 和 right 左右边界对应的 length = sum
notion image

并查集

利用每个数在 nums 中的下标,把下标和下标进行 union(),具体做法是看前一个数 nums[i]-1 和后一个数 nums[i]+1 在 map 中是否存在,如果存在就 union(),最终输出整个并查集中包含最多元素的那个集合的元素总数。