128. 最长连续序列

https://leetcode-cn.com/problems/longest-consecutive-sequence/

解法一：

用哈希表存储每个端点值对应连续区间的长度

若数已在哈希表中：跳过不做处理

若是新数加入： 取出其左右相邻数已有的连续区间长度 left 和 right

计算当前数的区间长度为：cur_length = left + right + 1

根据 cur_length 更新最大长度 max_length 的值

更新区间两端点的长度值

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        hash_dict = {}
        max_len = 0
        
        for num in nums:
            if num not in hash_dict:
                left = hash_dict.get(num-1, 0)  #左边区间长度，不存在则为0
                right = hash_dict.get(num+1, 0)  #右边区间长度，不存在则为0
                
                cur_len = left + right + 1
                max_len = max(max_len, cur_len)
                
                #更新区间两端点
                hash_dict[num] = cur_len   #注意
                hash_dict[num - left] = cur_len
                hash_dict[num + right] = cur_len
                #print(hash_dict, num, left, right)
        return max_len

二、并查集

“连续”可以理解为num与num+1的连通关系，巧妙转化为并查集问题

对每个数num，检查num+1是否存在，若存在将他们连通。

并查集的规模为n，每个节点为num的下标i（其实节点值取什么无所谓，主要是为了合并，只要不重合即可，取num也可，但num的范围太大且不一定连续，所以取i较合适）

将每个数存入map，key为num，值为i。然后遍历map。（为何不是遍历nums？因为nums可能有重复数字）

class UnionFind:
    # 构造函数传入totalNodes为总节点数
    def __init__(self, totalNodes):
        # parents[i]表示i的根，初始i的根为其自身
        self.parents = [i for i in range(totalNodes)]
        # 连通分量数
        self.count = totalNodes
        # 树的“重量”
        self.size = [1] * totalNodes
    # 合并连通区域是通过find来操作的, 即看这两个节点是不是在一个连通区域内.
    def union(self, node1, node2):
        root1 = self.find(node1)
        root2 = self.find(node2)
        # 不连通才合并
        if root1 != root2:
          	# 小树合并到大树
            if self.size[root1] > self.size[root2]:
                self.parents[root2] = root1
                self.size[root1] += self.size[root2]
            else:
                self.parents[root1] = root2
                self.size[root2] += self.size[root1]
            # 连通分量数减一
            self.count -= 1

    # 查找最终的根
    def find(self, node):
        while self.parents[node] != node:
            self.parents[node] = self.parents[self.parents[node]]
            node = self.parents[node]
        return node

    # 判断两个点是否连通
    def isConnected(self, node1, node2):
        return self.find(node1) == self.find(node2)

    # 返回连通分量个数
    def count(self):
        return self.count

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0: return 0
        uf = UnionFind(n)
        map = {}
        for i in range(n):
            map[nums[i]] = i
	   #若num和num+1都存在， 将他们连通
        for num in map:
            if num+1 in map:
                uf.union(map.get(num), map.get(num+1))
        #求连通分量的最大值
        res = 0
        for size in uf.size:
            res = max(res, size)

        return res