128. 最长连续序列
给定一个未排序的整数数组
nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为
O(n) 的算法解决此问题。示例 1：
输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是[1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9
提示：
0 <= nums.length <= 105
109<= nums[i] <= 109
法1 并查集
思路
并查集的思路，将挨着的元素union到一个集合中。同是，在做union的时候，统计每个集合中的元素。
题解
class Solution: def longestConsecutive(self, nums: List[int]) -> int: if len(nums) == 0: return 0 uf = Unionfind(len(nums)) hash_map = {} for i in range(len(nums)): # 消除nums中的重复数字 if nums[i] in hash_map: continue # 因为nums 中可能有负数，所以，存放到hash中的为下标, # 且进行union的也是下标 hash_map[nums[i]] = i if nums[i] - 1 in hash_map: uf.union(i, hash_map[nums[i]-1]) if nums[i] + 1 in hash_map: uf.union(i, hash_map[nums[i]+1]) res = 1 temp = uf.size for i in range(len(temp)): res = max(res, temp[i]) return res class Unionfind: def __init__(self, n): self.parent = [i for i in range(n)] self.size = [1 for _ in range(n)] def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): root_x = self.find(x) root_y = self.find(y) # 如果是一个集合，直接返回 if root_x == root_y: return if self.size[root_x] > self.size[root_y]: self.parent[root_y] =root_x self.size[root_x] += self.size[root_y] else: self.parent[root_x] = root_y self.size[root_y] += self.size[root_x]