刷题使我快乐,满脸开心.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
}