刷题使我快乐,满脸开心.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. 实际写出来因为多个条件分支,代码比较混乱
  2. 虽然结果是对的,但是超时了。。。

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

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

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

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

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

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

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

如此,问题就简单了

  1. 如果一个数字没有小1的数字存在,那么它就是这一段连续数字的起点,计算连续长度,尝试更新
  2. 如果一个数字有小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
}