## 题目地址

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

## 题目描述

```
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Accepted
200,786
Submissions
485,346

```

## 思路

这是一道最最长连续数字序列长度的题目， 官网给出的难度是`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), 代码见后面`代码部分`

## 关键点解析

- 空间换时间

## 代码

```js
/*
 * @lc app=leetcode id=128 lang=javascript
 *
 * [128] Longest Consecutive Sequence
 *
 * https://leetcode.com/problems/longest-consecutive-sequence/description/
 *
 * algorithms
 * Hard (40.98%)
 * Total Accepted:    200.3K
 * Total Submissions: 484.5K
 * Testcase Example:  '[100,4,200,1,3,2]'
 *
 * Given an unsorted array of integers, find the length of the longest
 * consecutive elements sequence.
 *
 * Your algorithm should run in O(n) complexity.
 *
 * Example:
 *
 *
 * Input: [100, 4, 200, 1, 3, 2]
 * Output: 4
 * Explanation: The longest consecutive elements sequence is [1, 2, 3, 4].
 * Therefore its length is 4.
 *
 *
 */
/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
  nums = new Set(nums);
  let max = 0;
  let y = 0;
  nums.forEach(x => {
    if (!nums.has(x - 1)) {
      y = x + 1;
      while (nums.has(y)) {
        y = y + 1;
      }
      max = Math.max(max, y - x); // y - x 就是从i开始到最后有多少连续的数字
    }
  });
  return max;
};
```