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

Constraints:

• 0 <= nums.length <= 105

• -109 <= nums[i] <= 109

解題

Runtime: 138 ms, faster than 75.35%

Memory Usage: 11.1 MB, less than 45.37%

func longestConsecutive(nums []int) int {
    if len(nums) == 0 { return 0 }
    
    m := make(map[int]bool) // 紀錄存在於 nums 內的數字
    
    for _, num := range nums {
        m[num] = true
    } 
    
    ans := 1
    
    for num := range m {
        if _, ok := m[num-1]; !ok {    // 是連續數列中最小的才開始找
            currLength := 1            // 目前的長度
            currNum := num             // 下一個要找的數字
            
            for {
                if _, ok := m[currNum+1]; ok {       // 找到了，長度+1、找下一個
                    currNum++
                    currLength++
                } else {
                    break
                }
            }
            
            if currLength > ans { ans = currLength }
        }
    }
  
    return ans
}