128.最长连续序列
128.1 题目
给定一个未排序的整数数组 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
示例 3：
输入：nums = [1,0,1,2]
输出：3
提示：
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
128.2 题解
方法一：哈希集合法
思路
题目要求 O(n) 时间复杂度，排序肯定不行（至少 O(n log n)）。关键在于：如何快速判断一个数是否在数组中？
用 HashSet！它可以 O(1) 查询，还能自动去重。
核心技巧：只从序列的起点开始计数。怎么判断一个数是不是起点？如果 x-1 不在集合中，那 x 就是某个连续序列的起点。
比如 [100,4,200,1,3,2]：
- 100 是起点（99不存在），向后找：100存在，101不存在，长度1
- 4 不是起点（3存在），跳过
- 200 是起点（199不存在），长度1
- 1 是起点（0不存在），向后找：1,2,3,4都存在，5不存在，长度4 ← 最大
这样每个数最多被访问两次（一次判断是否起点，一次被某个起点向后遍历时访问），时间复杂度 O(n)。
复杂度分析
- 时间复杂度：
O(n)，每个元素最多被访问两次 - 空间复杂度：
O(n)，HashSet 存储所有元素
代码
// 方法一：哈希集合法
// 核心思路：使用哈希集合存储所有数字，然后遍历集合寻找连续序列的起点
// 重点是找起点，往左边找如果有，那说明不是起点，直接跳过此次循环。
// 时间复杂度：O(n)，每个元素最多被访问两次
// 空间复杂度：O(n)，需要存储所有数字到哈希集合
// 优点：满足O(n)时间复杂度要求，实现相对高效
// 缺点：需要额外的空间存储哈希集合
static int LongestConsecutive1(int[] nums)
{
if (nums == null || nums.Length == 0)
return 0;
// 简化：直接用数组初始化哈希集合，自动去重
HashSet<int> set = new HashSet<int>(nums);
int result = 0; // 初始值设为0更合理
foreach (var item in set)
{
// 只有当前数字是序列起点（前一个数不存在），才统计
if (set.Contains(item - 1))
continue;
int tempResult = 1;
int val = item;
// 往后找连续数字，统计长度
while (set.Contains(++val))
{
tempResult++;
}
result = Math.Max(result, tempResult);
}
return result;
}
128.3 代码
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
#region 题目
// 给定一个未排序的整数数组 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
// 示例 3：
// 输入：nums = [1,0,1,2]
// 输出：3
// 提示：
// 0 <= nums.length <= 105
// -109 <= nums[i] <= 109
#endregion
#region 测试
// 示例 1
int[] nums1 = { 100, 4, 200, 1, 3, 2 };
int result11 = LongestConsecutive1(nums1);
Console.WriteLine($"示例1 方法1 输出：{result11}");
// 示例 2
int[] nums2 = { 0, 3, 7, 2, 5, 8, 4, 6, 0, 1 };
int result21 = LongestConsecutive1(nums2);
Console.WriteLine($"示例2 方法1 输出：{result21}");
// 示例 3
int[] nums3 = { 1, 0, 1, 2 };
int result31 = LongestConsecutive1(nums3);
Console.WriteLine($"示例3 方法1 输出：{result31}");
#endregion
}
#region 答案
// 方法一：哈希集合法
// 核心思路：使用哈希集合存储所有数字，然后遍历集合寻找连续序列的起点
// 重点是找起点，往左边找如果有，那说明不是起点，直接跳过此次循环。
// 时间复杂度：O(n)，每个元素最多被访问两次
// 空间复杂度：O(n)，需要存储所有数字到哈希集合
// 优点：满足O(n)时间复杂度要求，实现相对高效
// 缺点：需要额外的空间存储哈希集合
static int LongestConsecutive1(int[] nums)
{
if (nums == null || nums.Length == 0)
return 0;
// 简化：直接用数组初始化哈希集合，自动去重
HashSet<int> set = new HashSet<int>(nums);
int result = 0; // 初始值设为0更合理
foreach (var item in set)
{
// 只有当前数字是序列起点（前一个数不存在），才统计
if (set.Contains(item - 1))
continue;
int tempResult = 1;
int val = item;
// 往后找连续数字，统计长度
while (set.Contains(++val))
{
tempResult++;
}
result = Math.Max(result, tempResult);
}
return result;
}
#endregion
}
128.4 运行结果
示例1 方法1 输出：4
示例2 方法1 输出：9
示例3 方法1 输出：3
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
