A.每日一题——128. 最长连续序列

题目链接：128. 最长连续序列（中等）

算法原理：

解法：哈希表

23ms击败91.35%

时间复杂度O(N)

题目要求时间复杂度是O(N)，那么我们就不能直接调用Arrays.sort直接排序，因为这样的话时间复杂度会飙升到O(NlogN)

由于让求的是最长连续序列，重点在连续，意味着同样的数，只要出现一次就够用了，所以可以去重，省下大量的遍历

①把所有数全扔进Set容器里，这样可以用O(1)来判断这个数是否在nums中

②如果x-1在哈希集合中，那么就不能以x为起点了，因为以x-1为起点计算出的序列长度一定比以x为起点计算出的序列长度要长！所以直接跳过即可，可以避免大量的重复计算！

比如nums=[5,2,4,3]，从3开始找到的序列是3，4，5，而从2开始找到的是2，3，4，5

③小优化：当以当前x为起点找到的序列长度超过原数组长度一半时，那么就无需再找了，因为没有序列能比这个还长了，直接返回结果即可

Java代码：

class Solution { public int longestConsecutive(int[] nums) { Set<Integer> hash=new HashSet<>(); //把nums里的元素全扔哈希表里 for(int x:nums) hash.add(x); int ret=0; for(int x:hash){ //如果x前面还有更小的，那么当前x一定不能作最长连续子序列的起点，直接跳过 if(hash.contains(x-1)) continue; //x是序列的起点 int y=x+1; while(hash.contains(y)) y++; //循环结束之后，y-1是最后一个在哈希集合的数 //从x到y-1一共y-x个数 ret=Math.max(ret,y-x); //小优化：当前连续子序列长度超过原数组的一半时 //不可能再有比这个长的了，直接返回 if(ret*2>=hash.size()) break; } return ret; } }