## 题目地址(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), 代码见后面`代码部分`

## 关键点解析

- 空间换时间

## 代码

代码支持：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
            #  if 的作用是剪枝
            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://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)