简单易懂的leetcode 100题-第二篇 最长连续序列
前言
今天来到我们的第三道题， 不过索引是第二篇😄。
这道题是哈希表题目中的一个重要代表，也是经典的"连续子数组"类型问题之一。不过这里要注意，它考察的是「连续的数字」，不是连续的数组位置。
题目 128. 最长连续序列 【中等】
虽然标着中等，其实只要思路打开了，并不复杂。
属于那种：暴力不行，哈希秒杀 类型。
https://leetcode.cn/problems/longest-consecutive-sequence/description/
题目描述
给定一个未排序的整数数组 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 <= 10⁵-10⁹ <= nums[i] <= 10⁹
题目分析
1. 思考过程
-
暴力方法：先排序，然后找连续段。这种思路时间复杂度是
O(nlogn)，因为排序了，不符合 O(n) 的要求。 -
哈希法：用哈希表记录每个数出现没出现。
- 核心思路是只从“连续段的起点”开始往后数。
- 什么是连续段的起点？就是当前数
x，左边的x-1不存在。 - 从起点数出最长连续长度。
2. 为什么要从起点开始？
- 如果不是起点，比如中间某个数字，重复计算了。比如
2，既可以从1数，也可以从2数，浪费时间。 - 只从起点
1数，就只会数一遍[1,2,3,4]。
3. 举个例子
数组：[100,4,200,1,3,2]
- 把所有数字存到哈希表里。
- 遍历每个数字：
- 100：99不存在，是起点，往后数，没有101，长度1。
- 4：3存在，不是起点，跳过。
- 200：199不存在，是起点，长度1。
- 1：0不存在，是起点，数出 [1,2,3,4]，长度4。
- 3：2存在，跳过。
- 2：1存在，跳过。
最终最长长度就是4。
解题思路总结
一句话总结思路：
把所有数放到哈希表，遍历每个数，遇到起点就开始数，更新最长长度。
Java 代码实现
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
// 这里是O(n) ，下面也是O(n) ，两次O(n)计算时间复杂度的时候忽略常数项仍然是 O(n)。
for (int num : nums) {
set.add(num);
}
int longest = 0;
for (int num : set) { // 这里不能用 nums遍历。因为测试用例里面有大量重复数字的case，用nums遍历会超时。
// 只有当前数是起点时才开始往后找
if (!set.contains(num - 1)) {
int currentNum = num;
int currentStreak = 1;
while (set.contains(currentNum + 1)) {
currentNum++;
currentStreak++;
}
longest = Math.max(longest, currentStreak);
}
}
return longest;
}
}
C++ 代码实现
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> set(nums.begin(), nums.end());
int longest = 0;
for (int num : set) {
if (!set.count(num - 1)) { // 如果不存在num-1，才是起点
int currentNum = num;
int currentStreak = 1;
while (set.count(currentNum + 1)) {
currentNum++;
currentStreak++;
}
longest = max(longest, currentStreak);
}
}
return longest;
}
};
时间复杂度和空间复杂度分析
| 项目 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) |
每个元素最多被访问两次（一次放入 set，一次遍历/查找连续段） |
| 空间复杂度 | O(n) |
哈希表存储所有元素 |
易错点提醒
- 遍历的时候，一定要检查是不是连续段的起点（
num - 1不存在）。 - 不能排序再做！虽然排序可以解，但那是
O(nlogn)，题目要求是O(n)。 nums可能有重复元素，用Set去重！
总结
这道题虽然一开始看上去麻烦，其实掌握了 "只从起点数" 的思路以后，非常丝滑！
这类题目的核心是通过哈希表来O(1)查找信息，哈希表的使用也是以后做很多题目的基本功。
下一道题见 🚀！