longest-consecutive-sequence

https://leetcode.com/problems/longest-consecutive-sequence/

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(_n_) complexity.

Example:

Input:[100, 4, 200, 1, 3, 2]

Output:4

Explanation:The longest consecutive elements sequence is [1, 2, 3, 4] . Therefore its length is 4.

解题思路:

1.利用hashmap 存储
2.每次存储的时候判断 n-1 n+1 即当前元素的前后两个位置,是否有元素,
有的话将对应位置的数据++,然后将n 赋值为调整后的指针。
最后就能得到一个hashmap存储的指针地址
3.在每一步得到n 的大小都与max 进行比较。调整赋值。

该思路能得到一个完整的hashmap key =>pointer 。更适合拓展

以下是实现的代码

func longestConsecutive(nums []int) int {
    globalN := map[int]*int{}
    max := 0
    for _, v := range nums {
        if globalN[v] != nil {
            continue
        }
        //左侧非nil
        if globalN[v-1] != nil && globalN[v+1] == nil {
            //指针地址偏移
            *globalN[v-1] = *globalN[v-1] + 1
            globalN[v] = globalN[v-1] //以左侧指针为准
        } else if globalN[v+1] != nil && globalN[v-1] == nil {
            *globalN[v+1] = *globalN[v+1] + 1
            globalN[v] = globalN[v+1] //以右侧指针为准
        } else if globalN[v+1] != nil && globalN[v-1] != nil {
            //左侧的全跟上
            *globalN[v-1] = *globalN[v-1] + 1 + *globalN[v+1]
            //全部以左侧为准,所以修改的是最右侧的 为左侧指针
            globalN[v+*globalN[v+1]] = globalN[v-1] //右侧指针和左侧一样
            globalN[v] = globalN[v-1]               //中间和左侧 左侧一样都行
        } else {
            s := 1
            globalN[v] = &s
        }
        if *globalN[v] > max {
            max = *globalN[v]
        }
    }
    return max
}