企业官网建设流程全解析

一、题目描述

给定一个未排序的整数数组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 输入：nums = [1, 0, 1, 2] 输出：3

数据范围：

0 <= nums.length <= 10^5

-10^9 <= nums[i] <= 10^9

二、思路演进

这道题看似简单，但由于数据范围极大（10^9）且要求O(n)时间，很容易踩坑。下面记录三次尝试的演进过程。

尝试一：排序 + 相邻比较

直觉思路：先排序，然后遍历判断相邻元素是否差 1。

class Solution { public: int longestConsecutive(vector<int>& nums) { sort(nums.begin(), nums.end()); int ans = 0, num = 1; for (int i = 0; i < nums.size() - 1; i++) { if (nums[i+1] - nums[i] == 1) { num++; ans = max(ans, num); } else { num = 1; } } return ans; } };

存在的问题：

1. 时间复杂度不达标：排序需要O(n log n)，题目明确要求O(n)。

2. 重复元素处理错误：如[1, 1, 2]，nums[i+1] - nums[i] == 0会走else分支，导致num被错误重置。

3. 边界问题：空数组时nums.size() - 1在size_t下溢；单元素数组返回 0（正确应为 1）。

结论：思路直观但不满足要求，需要换方向。

尝试二：计数数组（桶思想）

直觉思路：用数组下标表示数字本身，值表示是否出现。然后扫描数组，统计连续非零段长度。

class Solution { public: int longestConsecutive(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<int> a(10000, 0); for (int i = 0; i < nums.size(); i++) { a[nums[i]]++; } // ... 扫描 a，找最长连续非零段 } };

存在的问题：

1. 数组大小硬编码错误：nums[i]范围是-10^9 ~ 10^9，开10000数组不仅会越界，还会漏掉负数和超大数。

2. sort冗余：使用计数数组后不需要排序，白白增加O(n log n)开销。

3. flag与num逻辑交叉混乱：多个if分支配合flag = -100的初始值，有大量死代码（flag == -1永不触发）。

进步点：已经意识到"用存在性代替相邻比较"可以规避重复元素问题，思路方向是对的。

结论：受限于数据范围，计数数组不可行，但"存在性查询"的想法需要保留，用哈希集合替代。

尝试三：哈希集合（正解）

核心观察：

对于任意一个连续序列[x, x+1, x+2, ..., x+k]，如果只从序列起点（即x-1不存在于数组中）出发，向后逐一判断x+1, x+2, ...是否存在，就能得到该序列的长度。

这样做的好处是：每个数字最多只会被访问一次——因为它要么是某个序列的起点，要么是被某个起点"顺带数过去"的，不会重复遍历。

算法步骤：

1. 将nums全部放入unordered_set，实现O(1)存在性查询并自动去重。

2. 遍历集合中每个数字cur：

   • 若cur - 1存在，则cur不是起点，跳过。

   • 若cur - 1不存在，则cur是起点，向后不断查找cur + 1, cur + 2, ...，统计当前序列长度。

3. 更新全局最大值ans。

代码实现：

class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> num_set; for (int i = 0; i < nums.size(); i++) { num_set.insert(nums[i]); } int ans = 0; for (unordered_set<int>::iterator it = num_set.begin(); it != num_set.end(); it++) { int cur = *it; // 只从序列起点开始统计 if (num_set.find(cur - 1) == num_set.end()) { int currentNum = cur; int num = 1; while (num_set.find(currentNum + 1) != num_set.end()) { currentNum++; num++; } if (num > ans) { ans = num; } } } return ans; } };

三、复杂度分析

四、边界情况

五、方法对比总结