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

解題思路:

先了解暴力破解的方式，我們可以用 O(nlogn) 的方式來解題，先排序再找出最長的連續序列。

使用 快速排序 或是 合併排序 時間複雜度都是 O(nlogn)。


def longestConsecutive(nums):
    if not nums:
        return 0
    nums.sort()
    max_length = 1
    current_length = 1
    for i in range(1, len(nums)):
        if nums[i] != nums[i - 1]:
            if nums[i] == nums[i - 1] + 1:
                current_length += 1
            else:
                max_length = max(max_length, current_length)
                current_length = 1
    return max(max_length, current_length)

但題目要求必須在 O(n) 的時間複雜度內解題，這時候就不能排序了…m… 換個方式，我們應該要找到一個最小值，一直往上找，直到找不到為止…最後再去比較目前的最大連續的值。 那找最小值的方法，用For一個一個找，找到之後看看他是否還有更小的值… 確實這樣在用Dict方式找O(1)，好像就完成了…最後別人比較好的做法是用Set。

def longestConsecutive(nums):
    if not nums:
        return 0
    nums_set = set(nums)
    max_length = 1
    for num in nums_set:
        if num - 1 not in nums_set:
            current_num = num
            current_length = 1
            while current_num + 1 in nums_set:
                current_num += 1
                current_length += 1
            max_length = max(max_length, current_length)
    return max_length