# 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`.

符合直觉的做法是先排序，然后用一个变量记录最大值，遍历去更新最大值即可，

代码：

```js
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:

```java
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:

```py
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:

```js
/**
 * @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 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://p.ipic.vip/chi7a9.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/128.longest-consecutive-sequence.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.