题目描述

给定一个未排序的整数数组 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

思路1

（排序+去重+快慢指针方法，leetcode可以过，但是时间复杂度不是 O(n) ）

一开始看到题目，肯定想到是先排序，然后使用快慢指针方法进行解决

排序后变成 【1，2,3,4,100,200】，然后慢指针指向连续序列的开头，快指针指向连续序列的结尾

当nums[i]!=nums[i-1]+1时，说明已经断开了，已经到达当前最大连续序列，计算max与当前最值中的最大者即可然后依次循环

还需要注意一种场景，排序后是0--1--1--2，这种有重复元素的需要去重后才能使用

代码1

class Solution {public int longestConsecutive(int[] nums) {//特殊场景if(nums==null||nums.length==0){return 0;}//循环从1开始，排除只有一个元素情况if(nums.length==1){return 1;}//排序Arrays.sort(nums);//去重nums = Arrays.stream(nums).distinct().toArray();//最大长度int maxLen=0;//当前序列长度int curLen=1;for(int i=1;i<nums.length;i++){//相邻两个数相差1，说明是连着的数，当前序列长度+1if(nums[i]==nums[i-1]+1){curLen++;}else{//不满足相差1 说明不是连着的数，就计算最大长度，然后将当前序列长度恢复成1maxLen= Math.max(maxLen,curLen);curLen=1;}}//最终要返回当前序列长度与maxLen的最大值return Math.max(maxLen,curLen);}
}

思路2

1、先把所有元素放入set中，去重

2、循环数组，当前元素的前一个数，

如果不在set中，那么就当该数是连续序列开头的元素，循环判断num[i]+1是否在数组中，存在就序列次数也增加。

如果在set中，说明当前元素不是连续序列的开头元素。

例如4--1--3--2，

4的前一个元素3在set中，4不是序列开头元素，所以直接跳过。

然后是1,1-1=0，0不在set中，那么把1当做是序列开头元素，接下来判断1+1=2，然后判断1+1=2在序列中，长度变2，然后2+1=3在序列中，长度变3，然后是3+1=4在set中，长度变4，然后4+1=5，不在序列中结束，此时连续的序列是1--2--3--4，最大长度4

代码2

class Solution {public int longestConsecutive(int[] nums) {Set<Integer> set = new HashSet<>();//添加到set中for(int num : nums){set.add(num);}int maxLen = 0;for(Integer num : set){//num-1不在set中，说明num是序列第一个元素if(!set.contains(num-1)){//当前序列长度int currentLen = 1;//当前值int cur=num;//当当前元素+1在set中while(set.contains(num+1)){//当前序列长度+1currentLen++;//当前值加1num=num+1;}//取最大值maxLen = Math.max(maxLen,currentLen);}}return maxLen;}
}

leetcode中示例代码是将while(set.contains(num+1))改写成while(set.contains(++num))，时间就快了很多，所以可以进行这样的优化，下边num也不需要再+1

class Solution {public int longestConsecutive(int[] nums) {Set<Integer> set = new HashSet<>();//添加到set中for(int num : nums){set.add(num);}int maxLen = 0;for(Integer num : set){//num-1不在set中，说明num是序列第一个元素if(!set.contains(num-1)){//当前序列长度int currentLen = 1;//当前值int cur=num;//当当前元素+1在set中while(set.contains(++num)){//当前序列长度+1currentLen++;}//取最大值maxLen = Math.max(maxLen,currentLen);}}return maxLen;}
}