128. 最长连续序列

mid 哈希

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

1
2
3
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

1
2
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

哈希

使用 HashSet 存放每个数字，使查询复杂度降为 $O(1)$；

遍历，找到一个不存在前驱数 x-1 的数 x，尝试寻找 x+1，x+2，……

 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
func longestConsecutive(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	numSet := make(map[int]bool, 0)
	for _, num := range nums {
		numSet[num] = true
	}
	maxLen := 1
	for num := range numSet {
		curNum := num
		curLen := 1
		if !numSet[num-1] {
            // 若不存在num-1，则以num为起点，向后一个个递增查找，记录长度
			for numSet[curNum+1] {
				curNum++
				curLen++
			}
			if curLen > maxLen {
				maxLen = curLen
			}
		}
	}
	return maxLen
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        hash = dict()
        for i in nums:
            hash[i] = True

        max_len = 1
        for num in nums:
            cur_len = 1
            if num - 1 in hash.keys():
                continue
            while num + 1 in hash.keys():
                cur_len += 1
                num += 1
            if cur_len > max_len:
                max_len = cur_len
        return max_len