Links

0128. 最长连续序列

题目地址(128. 最长连续序列)

https://leetcode-cn.com/problems/longest-consecutive-sequence/

题目描述

给定一个未排序的整数数组,找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

前置知识

  • hashmap

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

这是一道最最长连续数字序列长度的题目, 官网给出的难度是hard.
符合直觉的做法是先排序,然后用一个变量记录最大值,遍历去更新最大值即可,
代码:
if (nums.length === 0) return 0;
let count = 1;
let maxCount = 1;
// 这里其实可以不需要排序,这么做只不过是为了方便理解
nums = [...new Set(nums)].sort((a, b) => a - b);
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i + 1] - nums[i] === 1) {
count++;
} else {
if (count > maxCount) {
maxCount = count;
}
count = 1;
}
}
return Math.max(count, maxCount);
但是需要排序时间复杂度会上升,题目要求时间复杂度为 O(n), 那么我们其实可以不用排序去解决的。
思路就是将之前”排序之后,通过比较前后元素是否相差 1 来判断是否连续“的思路改为 不排序而是直接遍历,然后在内部循环里面查找是否存在当前值的邻居元素,但是马上有一个 问题,内部我们查找是否存在当前值的邻居元素的过程如果使用数组,时间复杂度是 O(n), 那么总体的复杂度就是 O(n^2),完全不可以接受。怎么办呢?
我们换个思路,用空间来换时间。比如用类似于 hashmap 这样的数据结构优化查询部分,将时间复杂度降低到 O(1)。
代码上,我们先将 nums 存到哈希表中。然后找所有序列的起点 x, 递增 x 尝试从 x 出发能达到的最大长度。
我们怎么知道哪些数字是序列的出发点呢? 比如数组 [1, 3, 2] 我们怎么知道 1 是起点呢? 我们只需要判断 x - 1 是否在哈希表中即可。
代码见后面代码部分

关键点解析

  • 从所有的序列起点(终点也行)开始尝试
  • 空间换时间

代码

代码支持:Java, Python,JS
Java Code:
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<Integer>();
int ans = 0;
for (int num : nums) {
set.add(num);
}
for(int i = 0;i < nums.length; i ++) {
int x = nums[i];
// 说明x是连续序列的开头元素
if (!set.contains(x - 1)) {
while(set.contains(x + 1)) {
x ++;
}
}
ans = Math.max(ans, x - nums[i] + 1);
}
return ans;
}
}
Python Code:
class Solution:
def longestConsecutive(self, A: List[int]) -> int:
seen = set(A)
ans = 0
for a in A:
t = a
# 说明 t 是连续序列的开头元素。加这个条件相当于剪枝的作用,否则时间复杂度会退化到 N ^ 2
if t + 1 not in seen:
while t - 1 in seen:
t -= 1
ans = max(ans, a - t + 1)
return ans
JS Code:
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function (nums) {
set = new Set(nums);
let max = 0;
let temp = 0;
set.forEach((x) => {
// 说明x是连续序列的开头元素。加这个条件相当于剪枝的作用,否则时间复杂度会退化到 N ^ 2
if (!set.has(x - 1)) {
temp = x + 1;
while (set.has(y)) {
temp = temp + 1;
}
max = Math.max(max, y - x); // y - x 就是从x开始到最后有多少连续的数字
}
});
return max;
};
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(N)$
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。