最长连续序列 (Longest Consecutive Sequence) - LeetCode 题解

题目描述

给定一个未排序的整数数组 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,1,2,3,4,5,6,7,8]。它的长度为 9。

示例 3：

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

解题思路

方法一：哈希集合（推荐）

哈希集合预处理：
- 将所有数字存入哈希集合中，实现O(1)时间复杂度的查找
- 去重处理，避免重复数字的影响
寻找连续序列：
- 遍历数组中的每个数字
- 对于每个数字，检查它是否是某个连续序列的起点（即num-1不在集合中）
- 如果是起点，则向后查找连续的数字，计算当前连续序列的长度
- 更新最长连续序列的长度
复杂度分析：
- 时间复杂度：O(n)，每个数字最多被访问两次（一次在哈希集合中，一次在连续序列查找中）
- 空间复杂度：O(n)，用于存储哈希集合

方法二：排序法（不满足O(n)要求）

排序数组：
- 先对数组进行排序
- 然后遍历排序后的数组，寻找最长连续序列
缺点：
- 时间复杂度为O(n log n)，不满足题目要求
- 仅作为对比思路提及

Go 代码实现

func longestConsecutive(nums []int) int {if len(nums) == 0 {return 0}// 创建哈希集合存储所有数字numSet := make(map[int]bool)for _, num := range nums {numSet[num] = true}longestStreak := 0// 遍历哈希集合中的每个数字for num := range numSet {// 检查当前数字是否是某个连续序列的起点if !numSet[num-1] {currentNum := numcurrentStreak := 1// 向后查找连续的数字for numSet[currentNum+1] {currentNum++currentStreak++}// 更新最长连续序列长度if currentStreak > longestStreak {longestStreak = currentStreak}}}return longestStreak
}func main() {// 示例测试nums1 := []int{100, 4, 200, 1, 3, 2}result1 := longestConsecutive(nums1)fmt.Println("Longest consecutive sequence length:", result1) // 输出: 4nums2 := []int{0, 3, 7, 2, 5, 8, 4, 6, 0, 1}result2 := longestConsecutive(nums2)fmt.Println("Longest consecutive sequence length:", result2) // 输出: 9nums3 := []int{1, 0, 1, 2}result3 := longestConsecutive(nums3)fmt.Println("Longest consecutive sequence length:", result3) // 输出: 3
}

测试用例

func TestLongestConsecutive(t *testing.T) {tests := []struct {input []intwant  int}{{[]int{100, 4, 200, 1, 3, 2}, 4},{[]int{0, 3, 7, 2, 5, 8, 4, 6, 0, 1}, 9},{[]int{1, 0, 1, 2}, 3},{[]int{}, 0},{[]int{1}, 1},{[]int{1, 3, 5, 7, 9}, 1},{[]int{1, 2, 3, 4, 5}, 5},{[]int{5, 4, 3, 2, 1}, 5},}for _, tt := range tests {got := longestConsecutive(tt.input)if got != tt.want {t.Errorf("longestConsecutive(%v) = %d, want %d", tt.input, got, tt.want)}}
}