128. Longest Consecutive Sequence

我第一时间读到这个题，我的最开始的思路是：

将整个数据序列，构建一个只有两层的跳表，在构建的过程当中，把序列最长的信息，放在队列的头部 value 中，如果当前的数据属于最头部，那就把后面的头部数据，移动到最前面的数据来。每一个数据序列，都有一个向上的指针，二级链表（跳表的第二层），如果两个序列相连，则将后面的序列头部的 value 移除，从二级链表移除，代表它已经被前面的队列所吸收。构建完成之后只需要将二级链表遍历一次即可。

我的思路会比较偏数据库，把整个队列在构建过程中流式的计算出来最长序列，类似并查集。但是题目并没有要求流式计算，并且希望能简单的得到答案，而无需涉及复杂的指针。

那么我们就使用传统思路了。

先把所有数据放在 map 中，然后遍历map：

对每个元素X 如果 X-1 存在，则忽略。
如果 X-1 不存在，则往后数，数到 X+N 断了则长度为 N

实现非常简单

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


func longestConsecutive(nums []int) int {
    maxSeq := 0
    m := make(map[int]int, len(nums))
    for _, number := range nums{
        m[number] = -1
    }

    for _, number := range nums {
        val := m[number]
        if val != -1{
            continue
        }
        _, hasPre := m[number - 1]
        if hasPre {
            continue
        }
        
        seqNumber := 1
        for i := number + 1; i < math.MaxInt64; i++{
            _, ok := m[i]
            if !ok{
                break
            }
            seqNumber += 1
        }
        if seqNumber >  maxSeq{
            maxSeq = seqNumber
        }

        m[number] = seqNumber
    }
    return maxSeq
}

性能足够好了