Leetcode:128. 最长连续序列

题目描述

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

思路

思路1 排序+遍历

在对数组进行排序后，依次遍历计算最长的连续序列，注意相等情况

思路2 hash表+初始值才遍历

使用一个hash表记录数组中存在的数字，每次都只计算当前数字在且该数字减一不在(避免重复遍历)，然后依次叠加计算最长连续序列

代码

代码1

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        
        Arrays.sort(nums);
        int result = 1;
        int temp = 1;
        for(int i = 1; i < nums.length; i++){
            if (nums[i] - nums[i - 1] == 1){
                temp += 1;
                if (temp > result){
                    result = temp;
                }
            }else if(nums[i] != nums[i - 1]){
                temp = 1; 
            }
        }
        
        return result;
    }
}

代码2

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        int result = 1;
        int temp = 1;
        
        HashSet numSet = new HashSet<>();
        for(int num: nums){
            numSet.add(num);
        }
        
        for(int num: nums){
            if (!numSet.contains(num - 1)){
                temp = 1;
                while (numSet.contains(num + 1)){
                    temp += 1;
                    num ++;
                }
                if (temp > result){
                    result = temp;
                }
            }
        }
        return result;
    }
}