审题:
需要我们在O(n)的时间复杂度下找到最长的连续序列长度
思路:
我们可以用两层for循环:第一层是依次对每个数据遍历,让他们当序列的首元素。
第二层是访问除了该元素的其他元素
但是此时时间复杂度来到了n^2,不满足我们的需求
实际上我们的这个思路存在很多多余的枚举:
eg:5 4 3 2 1
如果我们按照前面的方法枚举,有:
1.5为首元素,size为1
2.4为首元素,size为2
3.3为首元素,size为3
4.2为首元素,size为4
5.1为首元素,size为5
而实际上有效的只有第五次枚举,因为我们是用了整个连续序列(12345)的首元素1.其他的size都是一定小于以真正首元素为头的size的
所以,我们利用哈希表辅助实现减少枚举次数的目的
方法一:哈希表
找到连续序列的首元素的方法:利用哈希表快速查找是否存在当前值-1的元素,若有则说明不是首元素,否则则是
解题:
第一步:利用unordered_set记录去除了重复数据的nums数组
在讲解去重的原理前,我们先了解一下unordered_set:
unordered_set:无序的记录带有唯一性数据的容器,且可以根据他们的值在O(1)的时间复杂度内找到他们
数据具有唯一性的原因:与unordered_map不同的是,unordered_set的值同时也是键,而由于键具有不可修改和唯一的特性,数据既不能修改也是唯一的(但是允许插入删除)
于是去重的原理就是unordered_set的数据具有唯一性
第二步:核心代码
遍历nums数组的每个元素,若发现该数据不是连续序列的首元素(因为用了unordered_set才能在O(1)时间复杂度下找到),则不进行任何操作直接跳过。
若是连续序列的首元素,则在哈希表中存储的数据中去寻找属于他的序列的元素,并存储为cursize,最后与maxszie进行比较,将较大的给到maxsize
128. 最长连续序列 - 力扣(LeetCode)