前言

两周前的一场面试里，面试官出了一道算法题。

给定一个未排序的整数数组 nums，找出其中最长的连续子序列。

连续子序列指序列中相邻元素的值相差 1；值相同的元素也视为连续。返回该子序列本身。

请设计并实现时间复杂度为 $O(n)$ 的算法解决此问题。

示例：

输入：nums = [1, 2, 3, 4, 5, 1, 6, -1, 10, 11]

输出：[1, 1, 2, 3, 4, 5, 6]

计数排序

我想到的就是排序后再取连续递增子序列。题目要 $O(n)$，我想到的是桶排序，但一时想不出来，只好写了个计数排序勉强交差。还好面试过了。

typescript
function longestConsecutiveByCounting(nums: number[]): number[] {
  if (nums.length === 0) return [];
  let min = nums[0];
  let max = nums[0];
  for (const x of nums) {
    if (x < min) min = x;
    if (x > max) max = x;
  }
  const count: number[] = [];
  for (const x of nums) {
    const k = x - min;
    count[k] = (count[k] ?? 0) + 1;
  }
  let bestStart = 0;
  let bestLen = 0;
  let i = 0;
  while (i < count.length) {
    if (!count[i]) {
      i++;
      continue;
    }
    let j = i;
    while (j + 1 < count.length && count[j + 1]) j++;
    const len = j - i + 1;
    if (len > bestLen) {
      bestLen = len;
      bestStart = i;
    }
    i = j + 1;
  }
  const result: number[] = [];
  for (let k = bestStart; k < bestStart + bestLen; k++) {
    for (let c = 0; c < (count[k] ?? 0); c++) {
      result.push(k + min);
    }
  }
  return result;
}

桶排序

桶排序按值把元素分进桶里，下标取 x - min，所以下标越大值越大。遍历桶数组时，相邻几个桶里都有元素，就说明对应的值连续；取最长的一段，把桶里的元素依次取出来就是结果。

typescript
function longestConsecutiveByBucket(nums: number[]): number[] {
  if (nums.length === 0) return [];
  let min = nums[0];
  let max = nums[0];
  for (const x of nums) {
    if (x < min) min = x;
    if (x > max) max = x;
  }
  const buckets: number[][] = [];
  for (const x of nums) {
    const k = x - min;
    (buckets[k] ??= []).push(x);
  }
  let bestStart = 0;
  let bestLen = 0;
  let i = 0;
  while (i < buckets.length) {
    if (!buckets[i]) {
      i++;
      continue;
    }
    let j = i;
    while (j + 1 < buckets.length && buckets[j + 1]) j++;
    const len = j - i + 1;
    if (len > bestLen) {
      bestLen = len;
      bestStart = i;
    }
    i = j + 1;
  }
  const result: number[] = [];
  for (let k = bestStart; k < bestStart + bestLen; k++) {
    for (const x of buckets[k] ?? []) result.push(x);
  }
  return result;
}

哈希表

后面问了一下 AI 大人，AI 用 Map 记录每个值出现几次。遍历 Map 的所有 key，遇到 x - 1 不在 Map 里的，就以 x 为起点往后找连续的值，直到下一个值不在 Map 里。

typescript
function longestConsecutiveByHash(nums: number[]): number[] {
  if (nums.length === 0) return [];
  const count = new Map<number, number>();
  for (const x of nums) {
    count.set(x, (count.get(x) ?? 0) + 1);
  }
  let bestStart = 0;
  let bestLen = 0;
  for (const x of count.keys()) {
    if (count.has(x - 1)) continue;
    let len = 1;
    while (count.has(x + len)) len++;
    if (len > bestLen || (len === bestLen && x < bestStart)) {
      bestLen = len;
      bestStart = x;
    }
  }
  const result: number[] = [];
  for (let v = bestStart; v < bestStart + bestLen; v++) {
    const c = count.get(v)!;
    for (let k = 0; k < c; k++) result.push(v);
  }
  return result;
}

每个 key 只遍历一次，最多被扩展一次，所有 while 加起来不超过 $n$ 次。时间是 $O(n)$ 期望，空间 $O(n)$。

计数排序和桶排序都要把值域扫一遍，时间是 $O(n + R)$，$R = \text{max} - \text{min} + 1$。$R$ 远大于 $n$ 的时候，这两个写法就不合适了。

后记

当时一开始想的是排序，排完再检查连续子串。我没想到还能用哈希表，哈希表不用排序，避免了排序引起的复杂度增加。