2021-07-01:最长连续序列。一个未排序的arr,找出数字连续的最长序列的长度。输入:[100,4,1,20,3,2,50],输出:4。解释:最长数字连续序列是[1,2,3,4],所以长度是4。

福大大 答案2021-07-01:

连续区间头表,map1[5]=3,是5,6,7。
连续区间尾表,map2[5]=3,是3,4,5。
求map1中的value最大值,就是需要的返回值。
时间复杂度:O(N)。
空间复杂度:O(N)。

代码用golang编写。代码如下:

package main

import "fmt"

func main() {
    arr := []int{100, 4, 1, 20, 3, 2, 50}
    ret := longestConsecutive(arr)
    fmt.Println(ret)
}

func longestConsecutive(nums []int) int {
    map0 := make(map[int]int)
    ans := 0
    for _, num := range nums {
        if _, ok := map0[num]; !ok {
            map0[num] = 1
            preLen := 0
            posLen := 0
            if _, ok := map0[num-1]; ok {
                preLen = map0[num-1]
            }
            if _, ok := map0[num+1]; ok {
                posLen = map0[num+1]
            }
            all := preLen + posLen + 1
            map0[num-preLen] = all
            map0[num+posLen] = all
            ans = getMax(ans, all)
        }
    }
    return ans
}

func getMax(a int, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

执行结果如下:
图片


左神java代码