128. Longest Consecutive Sequence

題目

給定一個未排序的整數數位列 nums ，找出數字連續的最長序列（不要求序列元素在原陣列中連續）的長度。 請你設計並實現時間複雜度為 O(n) 的演演算法解決此問題。

題目大意

解題思路

Big O

時間複雜 : O(n) 空間複雜 : O(n)

來源

• https://leetcode.com/problems/longest-consecutive-sequence/description/
• https://leetcode.cn/problems/longest-consecutive-sequence/description/

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0128.Longest-Consecutive-Sequence/main.go

package longestconsecutivesequence

// 時間複雜 O(), 空間複雜 O()
func longestConsecutive(nums []int) int {
    m := make(map[int]struct{}, len(nums))
    for _, num := range nums {
        m[num] = struct{}{}
    }
    result := 0
    for v := range m {
        // 如果沒找到該數字的前一個數字, 則把該數字刀做連續序列的第一個數
        if _, ok := m[v-1]; !ok {
            length := 1
            for _, exit := m[v+length]; exit; _, exit = m[v+length] {
                length++
            }
            if result < length {
                result = length
            }
        }
    }
    return result
}

Benchmark