LeetCode每日刷题.09(128.最长连续序列)

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

解题思路：

? ? ? ? 给数组排序，排序完后，用for()循环将每一位与下一位作比较，若下一位元素等于当前元素+1则计数+1，若相同则不做动作，若大于当前元素+1则与目前计数器最大值max作比较，取大，然后计数器重新计数，最终返回计数器最大值即可。

?若数组排序后为严格递增数组(例如：[0,1,2,3,4])，则在循环后不会出现计数器最大值max与计数器n作比较，这样计数器最大值只会停留在初始化赋的值上，因此需要在循环后再加一个比较以防漏掉最大值。

代码实现：

class Solution {
    public int longestConsecutive(int[] nums) {
        //若长度为0，直接返回0
        if(nums.length==0) return 0;
        //数组排序
        Arrays.sort(nums);
        //创建一个计数变量n和存放最大计数的变量max
        //只要不是空数组，连续序列长度最少也是1，因此n初始化为1
        int max=1;
        int n=1;
        //for循环遍历整个数组
        for(int x=0;x<nums.length-1;x++){
            //若当前元素+1等于下一元素则，计数器n++
            if(nums[x]+1==nums[x+1]){
                n++;
            }
            //若大于当前变量+1则计数器n重置
            else if(nums[x]+1<nums[x+1]){
                //比较max与n的大小取大值
                max=Math.max(max,n);
                n=1;
            }
        }
        //若数组到最后都是连续的，则不会在循环中执行比较操作，所以需要循环后再比较一次
        max=Math.max(n,max);
        return max;
    }
}