这是我参与新手入门的第3篇文章。

题目描述

给定一个未排序的整数数组 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

思路分析

分析题目可知，数字 x 的最长连续序列其实是 x，x+1，x+2，……，x+n，其长度为 n+1，这样我们就可以便利数组，对每一个数字找出 x+n 不在数组中时 n 的值，此值就是 x 的连续序列长度。比较每次得到的长度取最大值，这就是我们要找的连续的最长序列的长度。

根据以上分析，我们可以发现：

• 重复的数字 x 对我们找出连续的最长序列是没有意义的，故我们可以使用 ES6 中新的数据类型 Set 为数组去重。
• 对于任意数字 x 的为起始的最长连续序列，不应该存在 x-1 在数组 nums 中，所以对于 x-1 在数组 nums 中的情况我们无需探索它的连续序列长度

还有下面我们来实现代码

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
const longestConsecutive = nums => {
  const numSet = new Set(nums);

  let longest = 0;

  for (const num of numSet) {
    if (!numSet.has(num - 1)) {
      let n = 1;
      while (numSet.has(num + n)) {
        n++;
      }

      longest = Math.max(n, longest);
    }
  }

  return longest;
};

首先我们使用 Set 对数组去重，接着我们定义了一个变量用来储存最长的连续序列长度，开始时我们将它置为 0；然后我们迭代 numSet，对每次迭代时的数字 num 判断是否在 numSet中存在 num-1，因为每个连续序列的起点都不应该存在 num-1 在 numSet 中；之后我们又定义了变量 n，用它表示数字 num 的连续序列长度，接下来我们开始探索数字 num 的连续序列的最大长度，将得出的 n 与已经记录的最大的长度比较，取较大的值；最后返回迭代数组完毕后的最大值。

总结

现在来总结一下，我们具体做了哪些：

1. 我们分析了什么是最长连续序列，即 x，x+1，x+2，……，x+n，长度为 n+1
2. 我们发现重复的数字对找出连续的最长序列是没有意义
3. 对于任意数字 x 的为起始的最长连续序列，不应该存在 x-1 在数组 nums 中
4. 我们编码代码实现了算法