每日一题：LeetCode-128. 最长连续序列

作者：半亩房顶

2023-12-27
北京
本文字数：1049 字
阅读完需：约 3 分钟

刷题使我快乐，满脸开心.jpg

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-consecutive-sequence/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给定一个未排序的整数数组 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

思路

最开始我的思路是空间换时间，用一个map记录数字是否存在，用另一个map记录每个数字以此数字为起始的最大连续长度。

但是实际写完之后意识到两个问题：

实际写出来因为多个条件分支，代码比较混乱
虽然结果是对的，但是超时了。。。

那么我们就需要一个更加简单的过滤机制：

避免重复计算
无视元素出现顺序，均能有效过滤且无副作用

副作用这道题没有太多要考虑的了，主要在于无视元素顺序过滤。

可以尝试换个思路，先看最期望的情况：

我们其实希望，只从每段连续数字的起始位置，其余未知不做计算

再进一步，如何判断一个数字是否为每段连续数字起始位置：

判断是否有比当前数字小1的数字存在，那么就能决定当前数字是否是起点了

如此，问题就简单了

如果一个数字没有小1的数字存在，那么它就是这一段连续数字的起点，计算连续长度，尝试更新
如果一个数字有小1的数字存在，那么它不是起点，就不需要处理了

至此代码也基本就出来了。老样子，细节在代码注释

代码

func longestConsecutive(nums []int) int {    numMap := make(map[int]bool, len(nums))    for _, num := range nums {        numMap[num] = true    }
    res := 0    for _, num := range nums {        // 如果数字不存在之前的值，那么就统计下        // 以此数开始的最大连续长度        // 尝试更新最大值        // 如果数字存在之前的值，那就不需要统计        // 总会从此段连续开始的数字进行统计        if !numMap[num-1] {            tmpNum := num + 1            tmpRes := 1            // 这里发现 += 1 会超时， ++ 不会超时            // 感觉有点意思，以后可以研究下            for numMap[tmpNum] {                tmpNum++                tmpRes++            }            if tmpRes > res {                res = tmpRes            }        }    }    return res}