最长连续序列

概要： 中等题，给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

心路历程

数组记录法（无法通过nlogn）

题目要求O(n)则只能循环一次，我想的是先去重和排序，然后用一个变量记录最长的连续次数，一个数组装连续数字，然后循环比较最终得到最后的结果：

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
  // 装连续数字的记录数组
  const recordArray = [];
  // 去重加排序
  const numsArr = Array.from(new Set(nums)).sort((a, b) => a - b);
  // 记录最长的连续次数
  let longestStreak = 0;
  for (let i = 0; i < numsArr.length; i++) {
    if (recordArray.length === 0 || numsArr[i - 1] + 1 === numsArr[i]) {
      // 如果记录数组为0，说明是第一次或者是前面连续的中断了
      recordArray.push(numsArr[i]);
      if (longestStreak < recordArray.length) {
        // 最长次数小于记录数组的长度，则覆盖掉
        longestStreak = recordArray.length;
      }
    } else {
      console.log(i, recordArray, numsArr[i], numsArr);
      if (longestStreak < recordArray.length) {
        longestStreak = recordArray.length;
      }
      // 中断则置空记录数组，且把当前的放进去
      recordArray.length = 0;
      recordArray.push(numsArr[i]);
    }
  }
  return longestStreak;
};

这个也可以用变量记录，不用数组记录

var longestConsecutive = (nums) => {
  if (nums.length === 0) return 0
  nums.sort((a, b) => a - b)
  let max = 1
  let count = 1
  for (let i = 0; i < nums.length - 1; i++) {
    let cur = i, next = i + 1
    if (nums[cur] === nums[next]) continue // 相同就跳过本次循环
    if (nums[cur] + 1 === nums[next]) { // 发现连续项 count++
      count++
    } else { // 否则，count重置1
      count = 1
    }
    max = Math.max(max, count)
  }
  return max
}

set查询

我们可以利用set查询为0(1)进行缩短时间，找每个数的右边也就是++存在多少个，就可以得出最多连续数字是多少。但是，真的有必要所有数都循环查询吗？只有起始点才需要查询，所以我们需要判断一下是不是起始点。这个方案只要区分你要的是索引还是数字本身就比较简单。

var longestConsecutive = function (nums) {
  // 利用set查询为O(1)
  const set = new Set(nums);
  let longestStreak = 0;
  for (let i = 0; i < nums.length; i++) {
    // 起始点才进入while循环,也就是左边有值的数
    if (!set.has(nums[i] - 1)) {
      let currentStreak = 1;
      let currentNum = nums[i];
      // 利用set查询右边有多少连续的
      while (set.has(currentNum + 1)) {
        currentStreak++;
        currentNum++;
      }
      longestStreak = Math.max(longestStreak, currentStreak);
    }
  }
  return longestStreak;
};

map两端对接法

每天都能学到骚操作，利用map存储数字，和数字连续的次数，不用更新所有数字的连续次数，只需更新两端的即可。每插入一个数字，就找这个的左右相邻数记录的连续次数，没有就默认连续次数为0，然后左连续次数+1+右连续次数就是目前的最长连续次数，然后更新当前的以及两端的记录，依次插入比较更新，最终得出最长连续次数。这里要注意，当前的还是要记录连续次数，不然相同的数字一进来，看到map上没有记录，然后在给左右两边更新一次就会重复。

var longestConsecutive = function (nums) {
  const map = new Map();
  let longestStreak = 0;
  for (let i = 0; i < nums.length; i++) {
    // 跳过相同的
    if (map.has(nums[i])) {
      continue;
    }
    // 找左右记录的连续数字
    const left = map.get(nums[i] - 1) || 0;
    const right = map.get(nums[i] + 1) || 0;
    const currentStreak = left + right + 1;

    longestStreak = Math.max(longestStreak, currentStreak);

    map.set(nums[i], currentStreak);
    map.set(nums[i] - left, currentStreak);
    map.set(nums[i] + right, currentStreak);
  }
  return longestStreak;
};

最终代码

var longestConsecutive = function (nums) {
  const map = new Map();
  let longestStreak = 0;
  for (let i = 0; i < nums.length; i++) {
    // 跳过相同的
    if (map.has(nums[i])) {
      continue;
    }
    // 找左右记录的连续数字
    const left = map.get(nums[i] - 1) || 0;
    const right = map.get(nums[i] + 1) || 0;
    const currentStreak = left + right + 1;

    longestStreak = Math.max(longestStreak, currentStreak);

    map.set(nums[i], currentStreak);
    map.set(nums[i] - left, currentStreak);
    map.set(nums[i] + right, currentStreak);
  }
  return longestStreak;
};

参考链接

• 128. 最长连续序列 - 力扣（LeetCode）