HHot 100C++ 图解

128. 最长连续序列

一句话套路set + 只在连续段起点向右扩

题目描述

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

示例 3:

输入:nums = [1,0,1,2]
输出:3

 

提示:

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

思路

时间O(n)
空间O(n)

思路

全部丢进 unordered_set。只对「一段连续区间的起点」展开向右延伸,起点判定 = set 里不存在 num-1。这样每个数最多被访问两次 -> O(n)。

关键

不做起点判定的话,[1,2,3,4] 会从 1 和 2 都往右扫,退化成 O(n^2)。

题目明确要求 O(n),所以「排序后扫描」的 O(n log n) 只能算备用解。

图解

0 0 3 1 7 2 2 3 5 4 8 5 4 6 6 7 0 8 1 9
数组(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/01_hash.cpp19 行
namespace lc0128 {
class Solution {
 public:
  int longestConsecutive(vector<int>& nums) {
    unordered_set<int> pool(nums.begin(), nums.end());  // 顺便去重
    int best = 0;
    for (int x : pool) {
      if (pool.count(x - 1)) continue;  // 不是起点,跳过
      int cur = x, len = 0;
      while (pool.count(cur)) {
        ++len;
        ++cur;  // 向右延伸
      }
      best = max(best, len);
    }
    return best;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q128_longest_consecutive11 行
lc0128::Solution s;
vector<int> a{100, 4, 200, 1, 3, 2};
CHECK_EQ(s.longestConsecutive(a), 4);  // 1,2,3,4
vector<int> b{0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
CHECK_EQ(s.longestConsecutive(b), 9);  // 0..8,重复的 0 不影响
vector<int> c{};
CHECK_EQ(s.longestConsecutive(c), 0);
vector<int> d{1};
CHECK_EQ(s.longestConsecutive(d), 1);
vector<int> e{-1, 0, 1};  // 含负数
CHECK_EQ(s.longestConsecutive(e), 3);

↑↓ 选择↵ 打开/ 随时唤起