PattySung

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

<解題>

使用 HashSet 存儲陣列中的所有元素
檢查它是否是一個連續序列的起點(即是否不存在比它小 1 的元素)
如果是起點，則從這個起點開始向後查找(set.contains(currentNum))，計算連續序列的長度。
更新最大長度，保留當前找到的最大連續序列長度


class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        
        for (int num : nums){
            set.add(num);
        }

        int maxCount = 0;

        for (int num : nums){
            int currentNum = num;
            int currSequence = 1;
            if (!set.contains(num - 1)){
                while (set.contains(currentNum + 1)){
                    currentNum++;
                    currSequence++;
                }
            }
            maxCount = Math.max(maxCount, currSequence);
        }
        return maxCount;
    }
}

Time: O(n) Space: O(n)


class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length==0) return 0;
        Arrays.sort(nums); //[1,2,3,3,4,100,200]

        int maxCount = 1;
        int currentCount=1;

        for(int i =1 ; i< nums.length; i++){
            if(nums[i]-nums[i-1]==1){
                currentCount++;
            } else if (nums[i]!= nums[i-1]){
                currentCount =1;
            }
            if(currentCount > maxCount){
                maxCount = currentCount;
            }
        }
    return maxCount;
    }
}

Time: O(nlog(n)) Space: O(1)

Leetcode-128. Longest Consecutive Sequence

<解題>