跳转至

LC128 - 最长连续序列

LongestConsecutiveSequence.go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
package HashTable

// 时间复杂度: O(n), 空间复杂度: O(n)
func longestConsecutive(nums []int) int {
    hashSet := make(map[int]bool)
    for _, num := range nums {
        hashSet[num] = true
    }
    result := 0
    for num := range hashSet {
        if hashSet[num-1] {
            continue
        }
        tmp := num
        for hashSet[tmp] {
            tmp++
        }
        result = max(result, tmp-num)
    }
    return result
}

最关键的部分就是11-13行，正是有了这里的剪枝算法时间复杂度才得以控制在O(n)。

除此以外必须遍历哈希表而非原始数组，因为原始数据中可能存在重复数字，在特定情况下(如: 1111...2345...)会使时间复杂度达到O(n^2)规模。