题目（难度：困难）：

给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。

示例

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

抛砖引玉

• 要求算法的时间复杂度为 O(n),即限制了只能循环一次；
• 先对数组排序
• 循环数组记录后一个元素等于前一个元素+1或者等于前一个元素的数量
  • 满足条件++，不然重置
  • 与之前记录的值取最大值
• 个人觉得和题目的限制，虽然排序是用数组原生的方法做的，但是应该是多了一次排序的循环

/**
 * @param {number[]} nums
 * @return {number}
 */
  var longestConsecutive = function (nums) {
      if (nums.length < 2) return nums.length;
      var _result = 1, middleValue = 1;
      nums.sort((a, b) => a - b)
      for (let index = 0; index < nums.length; index++) {
          if (nums[index] === nums[index + 1]) {
              continue // 跳出本次循环
          } else if (nums[index] + 1 === nums[index + 1]) {
              middleValue++
          } else {
              middleValue = 1
          }
          _result = Math.max(_result, middleValue);
      }
      return _result;
  };

官方答案

• 哈希表

我们考虑枚举数组中的每个数 x，考虑以其为起点，不断尝试匹配x+1,x+2,⋯ 是否存在，假设最长匹配到了 x+y，那么以 x 为起点的最长连续序列即为 x,x+1,x+2,⋯,x+y，其长度为 y+1，我们不断枚举并更新答案即可。

对于匹配的过程，暴力的方法是O(n) 遍历数组去看是否存在这个数，但其实更高效的方法是用一个哈希表存储数组中的数，这样查看一个数是否存在即能优化至O(1) 的时间复杂度。

仅仅是这样我们的算法时间复杂度最坏情况下还是会达到)O(n2)（即外层需要枚举 O(n) 个数，内层需要暴力匹配 OO(n) 次），无法满足题目的要求。但仔细分析这个过程，我们会发现其中执行了很多不必要的枚举，如果已知有一个x,x+1,x+2,⋯,x+y 的连续序列，而我们却重新从 x+1，x+2 或者是 x+y 处开始尝试匹配，那么得到的结果肯定不会优于枚举 x 为起点的答案，因此我们在外层循环的时候碰到这种情况跳过即可。

那么怎么判断是否跳过呢？由于我们要枚举的数 x 一定是在数组中不存在前驱数 x−1 的，不然按照上面的分析我们会从 x−1 开始尝试匹配，因此我们每次在哈希表中检查是否存在 x−1 即能判断是否需要跳过了。

var longestConsecutive = function(nums) {
    let num_set = new Set();
    for (const num of nums) {
        num_set.add(num);
    }

    let longestStreak = 0;

    for (const num of num_set) {
        if (!num_set.has(num - 1)) {
            let currentNum = num;
            let currentStreak = 1;

            while (num_set.has(currentNum + 1)) {
                currentNum += 1;
                currentStreak += 1;
            }

            longestStreak = Math.max(longestStreak, currentStreak);
        }
    }

    return longestStreak;   
};

高手在民间

• Set 的查找
  • Set 查找元素的时间复杂度是 O(1)，JS 的 Set 能给数组去掉重复元素
  • 将数组元素存入 set 中，遍历数组 nums
  • 如果 nums[i] - 1 存在于 set ，说明 nums[i] 不是连续序列的起点，跳过，继续遍历
  • 当前项没有“左邻居”，它就是连续序列的起点
  • 不断在 set 中查看 cur + 1 是否存在，存在，则 count +1
  • cur 不再有 “右邻居” 了，就算出了一段连续序列的长度

var longestConsecutive = (nums) => {

  const set = new Set(nums) // set存放数组的全部数字
  let max = 0
  for (let i = 0; i < nums.length; i++) {
    if (!set.has(nums[i] - 1)) { // nums[i]没有左邻居，是序列的起点
      let cur = nums[i]
      let count = 1
      while (set.has(cur + 1)) { // cur有右邻居cur+1
        cur++ // 更新cur
        count++ 
      }
      max = Math.max(max, count) // cur不再有右邻居，检查count是否最大
    }
  }
  return max
}

• 哈希表
  • 遍历原数组依次向map中存储原数组的值及其包含当前值的连续长度
  • 当前值的连续长度有两部分组成：1、小于当前值的连续长度，2、大于当前值的连续长度
  • 每次遍历结束同步map中的连续长度-供下次遍历中使用
  • 更新返回值max

var longestConsecutive = (nums) => {

  let map = new Map()
  let max = 0
  for (const num of nums) { // 遍历nums数组
    if (!map.has(num)) { // 重复的数字不考察，跳过
      let preLen = map.get(num - 1) || 0  // 获取左邻居所在序列的长度 
      let nextLen = map.get(num + 1) || 0 // 获取右邻居所在序列的长度 
      let curLen = preLen + 1 + nextLen   // 新序列的长度
      map.set(num, curLen) // 将自己存入 map
      max = Math.max(max, curLen) // 和 max 比较，试图刷新max
      map.set(num - preLen, curLen)  // 更新新序列的左端数字的value
      map.set(num + nextLen, curLen) // 更新新序列的右端数字的value
    }
  }
  return max
}

菜鸡的自白

优化说明:

• 没有考虑到可以使用set去重所有循环中需要单独判断存在重复值的问题
• 哈希表天然解决了重复值的问题，但是每个数据均需要统计连续长度还需要实时更新，感觉理解起来会繁琐一点
• 个人觉得‘Set 的查找’和官方的方法是比较有意思的

/**

 * @param {number[]} nums
 * @return {number}
 */
  var longestConsecutive = function (nums) {
      if (nums.length < 2) return nums.length;
      var _result = 1;
      for (let index = 0; index < nums.length; index++) {
          if (!nums.includes(nums[index] - 1)) {
              let middleValue = nums[index];
              let currentStreak = 1;
              while (nums.includes(middleValue + 1)) {
                  middleValue += 1;
                  currentStreak += 1;
              }
              _result = Math.max(_result, currentStreak);
          }
      }
      return _result;
  };