128. Longest Consecutive Sequence

难度: Medium

题目描述

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

Example 3:

Input: nums = [1,0,1,2]
Output: 3

 

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

解题思路

代码实现

解决方案

java

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // 使用HashSet替代TreeSet来提高查找效率至O(1)
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        int globalMaxLen = 0;

        for (int num : numSet) {
            // 如果num-1存在，则说明num不是某个序列的起点，跳过
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                // 向上扩展连续序列
                while (numSet.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                globalMaxLen = Math.max(globalMaxLen, currentStreak);
            }
        }

        return globalMaxLen;
    }

}