NOTES · 学习笔记

最长连续序列:起点判断 + 哈希查询

LeetCode哈希 · 中等约 3 分钟

题目

题目要求时间复杂度为 O(n),所以我们不能排序——排序的时间复杂度是 O(n log n)。那我们用哈希来解决:把数字放进哈希表中,然后遍历每个数字。怎么判断是不是起点?看 num-1 是否存在:如果上一个数字存在,说明当前这个数不是起点。

我们看示例:nums = [100,4,200,1,3,2],哈希表中存着 {100,4,200,1,3,2}。遍历:num=100,检查 99,存在吗?不存在,100 是起点,长度 1。num=4,检查 3,存在,说明 4 不是起点,跳过。

从起点开始找:定义一个 current 表示当前数,不断向后寻找连续数字,length 从 1 开始。也就是如果 num-1 不存在——当前数字是起点,就不断 num+1 查询下去,最后更新最大长度返回。

func longestConsecutive(nums []int) int {

    hash := make(map[int]bool)  // 定义一个哈希map用来存数字
    for _, num := range nums {  // 遍历nums中的值
        hash[num] = true        // 将nums中的值保存在hash中
    }
    maxLength := 0              // 定义一个最大长度,我们最后要返回最大长度
    for num := range hash {     // 哈希目前已经存放了nums中的值,我们遍历哈希
        if hash[num-1] {        // 如果当前数字的前一个数字也存在我们保存的hash中
            continue            // 跳过,因为它不是我们要找的第一个数
        }
        current := num          // 定义一个变量用来表示现在num的数是哪个
        length := 1             // 长度为1,因为当前包含起点数字
        for hash[current+1] {   // 当前 current 是连续序列的起点,不断寻找后面的数字
            current++           // 如果后面的数存在我们就自增
            length++
        }
        if length > maxLength { // 如果现在连续的长度大于最大长度
            maxLength = length  // 我们更新一下最大长度
        }
    }
    return maxLength
}