一、题目描述
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
二、思路讲解
很容易想到：排序后按顺序找等差数列的长度就行了。
需要注意的一点是，如果相邻位置数字相同，则跳过。
三、Java代码实现
class Solution { public int longestConsecutive(int[] nums) { if(nums.length<=1){ return nums.length; } int count = 1; //一个等差数列的长度 int big = 1; //所有等差数列的最大长度 Arrays.sort(nums); for(int i=0; i<=nums.length-2; i++){ int temp = nums[i+1]-nums[i]; if(temp==1){ count++; } else if(temp==0 && count!=1){ //相邻位置数字相同，则直接跳过 } else { big = Math.max(count, big); count = 1; } } big = Math.max(count, big); return big; } }
时间复杂度： O(NlogN)
空间复杂度： O(1)
四、思路优化
题目要求算法时间复杂度为 O(n)，我们想到使用hash表。hash表查找的时间复杂度为O(1)
将数字全部存入HashSet中，然后依次以每个数为等差数列的末尾，去集合中寻找小1的数字。如果找到，则再-1；如果找不到，则找下一个数字。
但是这样的做法，最坏情况会达到O(N^2)。我们需要进行一些判断。可以注意到，比如我们找的数字是4，然后依次去找3、2、1……，而假如nums中，还有一个3，那么我们还要再去找2、1、0……，事实上，找3以前的数字的这个操作早在找4的时候就已经做过了，就可以直接跳过了。
经过这样的优化，数组中的每个数字其实只被访问过一次，时间复杂度为 O(n)。
五、优化代码
class Solution { public int longestConsecutive(int[] nums) { Set<Integer> set = new HashSet<>(); for(int num : nums){ set.add(num); } int count = 1; //本次等差数列的长度 int big = 0; //所有等差数列的最大长度 for(int num : nums){ //如果集合中存在num+1，就放到算num+1的时候去算，这里就不做重复计算了 if(!set.contains(num+1)){ int temp = num - 1; //不断去找集合中小1的数字 while(set.contains(temp)){ count++; temp--; } big = Math.max(big, count); count = 1; } } return big; } }
时间复杂度： O(N)
空间复杂度： O(N)
