问题简述

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

示例：

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

要求算法的时间复杂度为 O(n)。

两种解法，天差地别

这个问题的一个经典解法是使用哈希表来优化查找。核心思路是：

  1. 将所有数字存入一个哈希表，实现 O(1) 的查找效率。
  2. 遍历数组，对于每个数字，如果我们发现它是一个连续序列的起点（即它的前一个数 num-1 不在哈希表中），我们就开始向后计算这个序列的长度。

然而，正是在这第二步的"遍历"中，一个细节决定了代码的性能是"超时"还是"通过"。

解法一：遍历原始数组（导致超时）

这是一个很自然会想到的实现方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// @lc app=leetcode.cn id=128 lang=golang
// 超时版本
func longestConsecutive(nums []int) (ans int) {
	hashTable := make(map[int]bool, len(nums))
	for _, num := range nums {
		hashTable[num] = true
	}

	// 关键点：这里遍历的是原始数组 nums
	for _, num := range nums {
		// 如果 num-1 存在，说明 num 不是序列的起点，跳过
		if hashTable[num-1] {
			continue
		}
		// 从 num 开始计算连续序列的长度
		currentLen := 0
		for i := num; hashTable[i]; i++ {
			currentLen++
		}
		ans = max(ans, currentLen)
	}
	return
}

性能瓶颈分析

这段代码的问题出在第二个 for 循环，它遍历的是原始数组 nums。如果 nums 中包含大量重复的元素，就会导致重复计算。

考虑一个最坏情况：
假设输入 nums 是 [1, 1, 1, 1, 1, 2, 3, 4, 5]。

  1. 哈希表 hashTable 会是 {1:true, 2:true, 3:true, 4:true, 5:true}。
  2. 当外层循环第一次遇到 1 时，它发现 hashTable[0] 不存在，于是开始计算序列长度，从 1 遍历到 5，计算出长度为 5。
  3. 当外层循环第二次、第三次、直到第五次遇到 1 时，它会一遍又一遍地重复上面的计算过程。

对于一个长度为 N 的数组，如果其中有 k 个重复的序列起点，而序列的平均长度为 L，那么时间复杂度会趋近于 O(k*L)，在最坏情况下 k 和 L 都可能与 N 相关，导致整体复杂度接近 O(N²)，从而在数据量大时超时。

解法二：遍历哈希表（AC 通过）

现在我们来看优化后的版本，改动非常微小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// @lc app=leetcode.cn id=128 lang=golang
// 通过版本
func longestConsecutive(nums []int) (ans int) {
	hashTable := make(map[int]bool, len(nums))
	for _, num := range nums {
		hashTable[num] = true
	}

	// 关键点：这里遍历的是哈希表的键
	for num := range hashTable {
		// 如果 num-1 存在，说明 num 不是序列的起点，跳过
		if hashTable[num-1] {
			continue
		}
		// 从 num 开始计算连续序列的长度
		currentLen := 0
		for i := num; hashTable[i]; i++ {
			currentLen++
		}
		ans = max(ans, currentLen)
	}
	return
}

性能提升分析

唯一的改动，就是将第二个循环的遍历对象从 nums 数组换成了 hashTable。

为什么这个改动如此关键？
因为哈希表（在 Go 中是 map）的键（key）是唯一的。当我们将 nums 存入 hashTable 时，所有重复的元素都被自然地去除了。

for num := range hashTable 遍历的是 nums 数组中所有不重复的元素。

回到刚才的例子 [1, 1, 1, 1, 1, 2, 3, 4, 5]：

  1. hashTable 依然是 {1:true, 2:true, 3:true, 4:true, 5:true}。
  2. 当外层循环遍历到键 1 时，它会计算一次序列长度（为 5）。
  3. 当遍历到 2, 3, 4, 5 这些键时，因为它们的前一个数（num-1）都在哈希表中，所以都会被 continue 语句直接跳过。

这种方法巧妙地保证了，每一个连续序列只会被其起点计算一次。每个数字最多被访问两次（一次是外层循环的检查，一次是内层循环的递增），因此总的时间复杂度是严格的 O(n)。

方法比较与总结

方面 解法一：遍历原始数组 解法二：遍历哈希表
时间复杂度 最坏 O(n²) O(n)
空间复杂度 O(n) O(n)
核心差异 遍历含重复元素的数组 遍历去重后的键集合
结果 超时 通过

关键收获

这个例子生动地告诉我们：

在设计算法时，选择正确的遍历对象和利用数据结构（如哈希表）的内生特性（如键唯一性）至关重要。一个看似微不足道的改动，可能就是 O(n²) 和 O(n) 的区别。

下次遇到需要去重和查找的场景时，记得优先考虑遍历哈希表本身，而不是遍历原始的、可能含大量重复元素的输入数据。