Leetcode hot128 最长连续序列：排序解法杂谈
题目：给定一个未排序的整数数组 nums，找出数字连续的最长序列的长度（序列元素在原数组中不要求连续）。要求时间复杂度为 O(n)（进阶要求）。
本文讨论的解法不满足进阶要求，时间复杂度为 O(n log n)，但实现简洁、细节清晰，值得作为分析的样本。
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if (nums.empty()) return 0;
sort(nums.begin(), nums.end());
int ans = 1;
int cnt = 1;
for (int i = 1; i < nums.size(); ++i) {
// 重复数字，跳过
if (nums[i] == nums[i - 1]) continue;
// 连续
if (nums[i] == nums[i - 1] + 1) ++cnt;
// 断开，重新开始
else cnt = 1;
ans = max(ans, cnt);
}
return ans;
}
};
化归：从"找序列"到"数区间"
这道题的原始形态是"无序集合中找连续数字"，直接处理需要反复在集合中判断"某个数的邻居是否存在"，自然导向哈希表。而排序解法选择了另一条路径：先花 O(n log n) 把数组排好序，最长的连续序列就坍缩成数组中一段相邻差为 1 的连续区间，问题随之退化为一次线性扫描中的计数。
这类"先预处理、再简化问题"的思路在算法题中极为常见。排序、前缀和、单调栈本质上都是预处理手段：投入一定的代价，换取后续问题的结构化。此处用 O(n log n) 的排序换来了 O(n) 且逻辑极简的扫描，这笔交换在多数场景下是划算的。
一个容易缺失的分支：重复数字
解法中最容易被忽略的是 if (nums[i] == nums[i - 1]) continue; 这一行。
考虑 {1, 2, 2, 3}：排序后遇到第二个 2 时，它既不等于前值（非重复分支），也不等于前值加 1（非连续分支），会落入"断开"分支，把正在计数的序列错误地重置为 1，最终得到错误答案。重复元素的语义应当是"对序列长度无影响"，因此正确处理方式是跳过，而非重置。
一个值得注意的细节是分支顺序：必须先判断重复、再判断连续。若顺序颠倒，重复元素会先落入"断开"分支，同样的错误仍然会发生。这类细节没有高深的原理，却直接决定代码的正确性，也往往是面试官区分"写得出"与"写得对"的观察点。
空数组：一个一行代码的边界
if (nums.empty()) return 0; 同样不可省略。若缺少该判断，空数组会走完排序与初始化，返回初始值 ans = 1，而正确答案是 0。边界条件的初始值设定与特殊情况的处理，往往比主体逻辑更容易出错——主体逻辑在测试中通常覆盖充分，边界则不然。
与哈希解法的对比
满足进阶要求的标准做法是哈希集合：所有数字入 unordered_set，只从"不存在 x−1 的数字"（即每段连续序列的起点）开始向后枚举 x+1、x+2……由于每个数字至多被访问两次，总体 O(n)。
两种解法的取舍可以从三个角度看：
- 时间复杂度：排序解法 O(n log n) 不满足进阶要求；哈希解法 O(n) 达标。
- 常数与缓存：排序解法对连续内存做顺序扫描，缓存局部性极佳；哈希解法的
unordered_set存在哈希开销与指针跳转，实际运行中两者差距常小于理论差距。此外unordered_set在最坏情况下（哈希冲突严重）会退化到 O(n²)，这是面试中可以主动提及的加分点。 - 实现难度：排序解法十几行、无复杂数据结构；哈希解法需要正确处理"只从段起点开始枚举"的剪枝逻辑，出错概率更高。
面试策略
基于上述对比，面试中的合理顺序是：先给出排序解法——它正确、简洁，能快速建立讨论基础；随后主动指出其不满足 O(n) 的进阶要求，并给出哈希解法；最后补充哈希冲突退化的讨论。这一流程展示了"先交付正确解，再优化"的工程习惯，比一上来就追求最优解、却在细节上出错的做法更为稳妥。
结语
排序解法本身并无精妙之处，它的价值在于完整地呈现了一个小型解题范本：通过预处理化归问题主体、通过 continue 分支处理重复这一语义细节、通过提前返回处理空数组这一边界条件、并在复杂度上留下明确的优化方向。刷题的意义未必在于记住每道题的最优解，而在于这类范本的积累。