128. Longest Consecutive Sequence

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Constraints:

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

Code

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) return 0;
        
        int res = 1;
        HashSet<Integer> set = new HashSet<>();

        for(int num : nums){
            set.add(num);
        }

        for(int i = 0; i < nums.length; i++){
            int num = nums[i];
            
            if(set.contains(num)){
                int upperNum = 0;
                int lowerNum = 0;
                set.remove(num);

                // upper elements
                while(set.contains(num + upperNum + 1)){
                    set.remove(num + upperNum + 1);
                    upperNum++;
                }

                while(set.contains(num - lowerNum - 1)){
                    set.remove(num - lowerNum - 1);
                    lowerNum++;
                }

                res = Math.max(res, 1 + lowerNum + upperNum);
            }
        }

        return res;
    }
}