第3题最长连续序列

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

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

示例 1：

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

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

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109

解题思路

创建一个哈希表 numSet，用于存储数组中的每个数字。
遍历数组 nums，将数组中的每个数字存储到 numSet 中，并初始化 maxLength 为 0。
对于数组中的每个数字 num：

如果 num-1 存在于 numSet 中，说明当前数字已经在之前的某个连续序列中被处理过，因此跳过。
否则，从当前数字 num 开始，向右扩展，计算连续序列的长度，并更新 maxLength。

返回 maxLength，即为最长连续序列的长度。

时间复杂度分析

哈希表构建：遍历数组 nums 并将其中的元素存储到哈希表 numSet 中，这一步操作的时间复杂度为 O(n)，其中 n 为数组的长度。

遍历数组并计算最长连续序列：对于每个数组元素，最多只会被访问两次：一次作为起始数字向右扩展，另一次作为中间数字被跳过。因此，整个算法的时间复杂度为 O(n)。

综上所述，该算法的时间复杂度为 O(n)。

golang代码实现

func longestConsecutive(nums []int) int {
    numSet := make(map[int]bool)
    for _, num := range nums {
        numSet[num] = true
    }
    maxLen := 0
    for num := range numSet {
        if numSet[num-1] {
            // 如果 num-1 存在于 numSet 中，说明当前数字已经在之前的某个连续序列中被处理过，因此跳过
            continue
        }
        currentNum := num
        currentLen := 1
        // 从起始点开始向上递增检查连续的数字
        for numSet[currentNum+1] {
            currentNum++
            currentLen++
        }
        // 更新最大长度
        if currentLen > maxLen {
            maxLen = currentLen
        }
    }
    return maxLen
}