003.最长连续序列

• 128.最长连续序列
  • 哈希表
  • 动态规划

最长连续序列 - 哈希表

func longestConsecutive(nums []int) int {
	res := 0
	has := make(map[int]bool, len(nums))
	for _, num := range nums {
		has[num] = true
	}
 
	for num := range has {
		if !has[num - 1] {
			cur := num
			length := 1
			for has[cur + 1] {
				cur++
				length++
			}
			if length > res {
				res = length
			}
		}
	}
 
	return res
}

最长连续序列 - 动态规划

func longestConsecutive(nums []int) int {
    res := 0
    // 1. num 在哈希表是否存在
    // 2. 端点元素的最长连续序列长度
    has := map[int]int{}
    for _, num := range nums {
        if has[num] != 0 {
            continue // 存在，之前已经算过了，跳过
        }
        left := has[num - 1]
        right := has[num + 1]
        length := left + 1 + right
        // 标记存在
        has[num] = 1
 
		// 端点元素的最长连续序列长度
        has[num - left] = length
        has[num + right] = length
        if length > res {
            res = length
        }
    }
    return res
}

首先，定义一个哈希表（用于判断某个数是否存在哈希表中）

然后遍历数组

如果当前数 num 存在哈希表，那么跳过

如果当前数 num 不存在哈希表中，那么查找 num-1和 num+1这两个数是不是在哈希表中

比如 num 是5

1234 678 都在哈希表中

遍历数组的时候，遇到1234678都会掠过

此时哈希表中，1的位置和4存的值都是4（证明1或者4所在的连续长度是4）

同理 6和8存的值都是3

那么此时5进来之后，看看4和6在不在哈希表内，如果在的话，一定是端点，一定能获取到值

所以5进来之后，发现左边有4个连续的，右边有3个连续的，加上自己一个，那么组成一个大连续的

4+1+3 = 8

所以要更新当前最长连续串的端点，也就是1的位置（5-4），8的位置（5+3），更新长度为8

只需要端点存值就行，因为端点中的值在遍历的时候如果在哈希表中就会略过

如果这个时候9又进来，那么它获取到8的位置有8，10的位置有0

更新连续子串长度（8+1+0）

所以更新左端点1（9-8）的值为9，右端点9（9+0）的值为9