128. Longest Consecutive Sequence

Question

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Solution 1

哈希表，先将所有元素加入哈希表。
然后遍历哈希表，如果表内没有当前数字-1时（没有更小的连续数字），则将temp初始化为1。
当表内有下一个连续数字时，将temp和curNum增加1。

当没有下一个连续数字时，更新结果到res上。

Code

class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        
        for(int num : nums){
            set.add(num);
        }
        
        int res = 0;
        
        for(int num : set){
            if(!set.contains(num - 1)){
                int temp = 1;
                int curNum = num;
                while(set.contains(curNum + 1)){
                    temp++;
                    curNum++;
                }
                res = Math.max(res, temp);
            }
        }
        return res;
    }
}

Solution 2

先排序，再遍历。
维护一个最大长度res。
用一个temp参数记录连续长度。
如果当前值是上一个值+1，则temp+1。
如果当前值等于上一个值，则continue。
其他情况则更新最大长度res，并将temp恢复为1。

Code

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) return 0;
        Arrays.sort(nums);
        int res = 0, temp = 1;
        
        for(int i = 1; i < nums.length; i++){
            if(nums[i] == nums[i-1] + 1){
                temp++;
            }
            else if(nums[i] == nums[i-1]){
                continue;
            }
            else{
                res = Math.max(res, temp);
                temp = 1;
            }
        }
        res = Math.max(res, temp);
        
        return res;
    }
}