寻找最长连续序列

题解思路

本题的目标是找到数组中最长的连续整数序列，并且要求算法的时间复杂度为 $O(n)$。可以使用 哈希集合（HashSet） 来实现高效查找，从而避免排序带来的 $O(n \log n)$ 复杂度。

解题方法

方法：哈希表 + 贪心

1. 构建哈希集合
   • 由于查找某个元素是否存在的操作在哈希表中是 $O(1)$ 复杂度，因此可以使用 set 存储数组中的所有数，方便后续查询。

Leetcode 3.最长连续序列-原题链接

题目内容

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

请你设计并实现时间复杂度为$O(n)$的算法解决此问题。

输入描述

输入共两行。

• 第一行为两个个整数$n$，代表数组$nums$的长度。

• 第二行为$n$个整数$nums_0,nums_1,...,nums_{n-1}$，数字之间以空格分隔。

输出描述

输出一个整数，代表答案。

样例1

输入

6
100 4 200 1 3 2

输出

4

说明

最长数字连续序列是 $[1, 2, 3, 4]$。它的长度为$4$。

样例2

输入

10
0 3 7 2 5 8 4 6 0 1

输出

9

样例3

输入

4
1 0 1 2

输出

3

提示

• $0 <= nums.length <= 10^5$

• $-10^9 <= nums[i] <= 10^9$