# LeetCode: 128. 最长连续序列¶

## 1、题目描述¶

输入: [100, 4, 200, 1, 3, 2]



## 2、解题思路¶

• 使用并查集
• 首先将数组去重并映射为相应的索引值
• 每一次遇到一个数前后值存在，就将对应索引值进行更新
• 并查集需要同时保存集合中元素的数量
class DFU:
def __init__(self, length):
self.data = list(range(length))
self.size = [1] * length

def find(self, x):
if self.data[x] != x:
self.data[x] = self.find(self.data[x])
return self.data[x]

def union(self, x, y):
xp = self.find(x)
yp = self.find(y)
if xp != yp:
if self.size[xp] > self.size[yp]:
self.size[xp] += self.size[yp]
self.data[yp] = xp
else:
self.size[yp] += self.size[xp]
self.data[xp] = yp

def count(self):
res = 0
for index, i in enumerate(self.data):
if index == i:
res += 1
return res

class Solution:
def longestConsecutive(self, nums: [int]) -> int:
if not nums:
return 0
res = 0
num_mapping = {}
pos = 0
for value in nums:
if value not in num_mapping:
num_mapping[value] = pos
pos += 1

d = DFU(pos)
for key, value in num_mapping.items():
if key - 1 in num_mapping:
d.union(value, num_mapping[key - 1])
if key + 1 in num_mapping:
d.union(value, num_mapping[key + 1])

res = max(res, d.size[d.find(value)])
return res