2020--08--23 数组里的最大连续数

给定一个无序的整数类型数组，求最长的连续元素序列的长度。
例如：
给出的数组为[100, 4, 200, 1, 3, 2],
最长的连续元素序列为[1, 2, 3, 4]. 返回这个序列的长度：4
你需要给出时间复杂度在O（n）之内的算法

这道题我想到的有两种做法：
1、用一个辅助数组，记录下来数组每个位置对应的连续数字长度，最后取最大值（后面可以省取数组，但这样做的通过率95%）

import java.util.*;


public class Solution {
    public boolean contain(int[] num,int value ){//contain用来查看value是不是再num[]里面
        for (int i = 0; i < num.length; i++) {
            if (value==num[i])return true;
        }
        return false;
    }
    //这道题的思路是用maxLength来跟进每一个索引值对应的连续长度，max随时跟进找到maxLength的最大值就是我们的答案
    public int longestConsecutive (int[] num) {
        int maxLength=1;//maxLength用来跟进
        int max = 0;//max是跟进我们的答案
        for (int i = 0; i < num.length; i++) {
            int index=1;//index是用来控制数组索引位置num[i]+index++的连续个数，如果num[i]+1存在了就往后找num[i]+2...
            while(true){
                if (contain(num,num[i]+index++)){//死循环，如果数组里有num[i]+index，那么maxLength加1
                    maxLength++;
                }else{//否则与max比较进行替换
                    if ( maxLength > max) {
                        max =maxLength;
                    }
                    maxLength=1;//maxLength归1
                    break ;
                }
            }
        }
        System.out.println(max);
        return max;
    }
}

2、用Arrays.sort排序，接下来找最长连续长度

import java.util.*;

public class Solution {
    public int longestConsecutive (int[] num) {
        Arrays.sort(num);//1、排序
        int maxLength=1;
        int max=1;
        for (int i = 0; i < num.length-1; i++) {//2、遍历
            if (num[i]==num[i+1]){//如果第i项=第i+1项，继续循环
                continue;
            }else if (num[i]==num[i+1]-1){//递增1，maxLength++
                maxLength++;
                 if (max<maxLength){
                    max = maxLength;
                }
            }else{//否则 maxLength归1，继续遍历
                maxLength=1;
            }
        }
        return max;
    }
}

第二钟相对比较简单，通过率也100，第一种的话手撕底层源码，时间复杂度也比较高