力扣hot3--并查集+哈希

第一想法是排个序然后遍历一遍，but时间复杂度就超啦

并查集居然与哈希结合了（）

已经好久没用过并查集了，，，我们用哈希表f_node中来记录原结点的父节点，其中key是原结点，value是父节点。我们用哈希表cnt来记录原结点所在集合的元素数目（只有这一集合的父节点的cnt才有效，即我们只维护父节点cnt的正确性），其中key是原结点，value是集合中元素的数目。

用哈希表来记录的好处是可以直接用.count()来查看是否存在临近元素：我们遍历nums中的每一个元素，依次判断元素值-1和元素值+1是否存在于某个集合中，如果存在，那就和元素值所在的集合合并。用res来维护最终结果。

class Solution {
public:int res=1;unordered_map<int,int> f_node;unordered_map<int,int> cnt;int find(int x){if(f_node[x]==x){return x;}f_node[x]=find(f_node[x]);return f_node[x];}void union_xy(int x,int y){int f_x=find(x);int f_y=find(y);if(f_x==f_y){return ;}f_node[f_x]=f_y;cnt[f_y]+=cnt[f_x];res=max(res,cnt[f_y]);}int longestConsecutive(vector<int>& nums) {if(nums.size()==0){return 0;}for(auto i:nums){f_node[i]=i;cnt[i]=1;}for(auto i:nums){if(f_node.count(i-1)){union_xy(i-1,i);}if(f_node.count(i+1)){union_xy(i,i+1);}}return res;}
};

---

简单注意一下：i 分别是nums中的数值

for(auto i:nums){if(f_node.count(i-1)){union_xy(i-1,i);}if(f_node.count(i+1)){union_xy(i,i+1);}
}

python3版本：

class Solution:res=1f_node={}cnt={}def find(self,x):if self.f_node[x]==x:return xself.f_node[x]=self.find(self.f_node[x])return self.f_node[x]def union_xy(self,x,y):f_x=self.find(x)f_y=self.find(y)if f_x==f_y:returnself.f_node[f_x]=f_yself.cnt[f_y]+=self.cnt[f_x]self.res=max(self.res,self.cnt[f_y])def longestConsecutive(self, nums: List[int]) -> int:self.res=1self.f_node={}self.cnt={}if len(nums)==0:return 0for i in nums:self.f_node[i]=iself.cnt[i]=1for i in nums:if i-1 in self.f_node:self.union_xy(i-1,i)if i+1 in self.f_node:self.union_xy(i,i+1)return self.res

---

看某个元素是否在列表中：直接用 in , 判断一个列表用 len() 即可