给定一个未排序的整数数组nums找出数字连续的最长序列不要求序列元素在原数组中连续的长度。请你设计并实现时间复杂度为O(n)的算法解决此问题。为什么用哈希集合:这道题的核心操作只有一个——判断某个数存不存在。只需要键,不需要任何值,所以用 set 而不是 map。哈希集合能 O(1) 回答存在性,还自动去重,正好满足 O(n) 的要求。思路:把全部数字放进集合。遍历每个数 x,若 x-1 也在集合里,说明 x 不是起点,跳过;若 x-1 不在,说明 x 是起点,就往后枚举 x1、x2…,终点减起点得到长度,更新答案。class Solution { public: int longestConsecutive(vectorint nums) { // 全部入集合,自动去重,O(1)查存在 unordered_setint st(nums.begin(),nums.end()); int ans0; for(auto x:st) // 遍历集合中每个数 { if(st.contains(x-1))continue; // x-1存在,说明x不是起点,跳过 int yx1; // x是起点,从x1开始往后枚举 while(st.contains(y))y; // 找到第一个不存在的数y ansmax(ans,y-x); // 序列长度y-x,更新答案 } return ans; } };Q1:代码里明明有 while 循环,为什么时间复杂度还是 O(n)?时间复杂度到底由什么决定?时间复杂度由核心操作的总次数决定,不是看嵌套层数。while 只在 x 是序列起点时才执行,每条连续序列只被枚举一次,所有序列长度之和 ≤ n,所以内层总共 O(n) 次,加上外层 O(n),实际是 2n 次操作,但大 O 记号忽略常数系数,所以记作 O(n)。。如果去掉起点判断,每个数都枚举,才会退化成O(n²)。Q2:排序的复杂度是 O(n log n),比 O(n) 大,但实际跑起来,示例这种小数据排序反而比哈希快,那实际项目里怎么选?复杂度描述的是大数据下的增长趋势,小数据时排序常数小、缓存友好,确实可能更快,但像示例这种规模没有实际意义。项目里:数据量小选简单清晰的排序;有线性硬性要求才用哈希;还要考虑空间——哈希要 O(n) 额外空间,排序可以原地。原则是先用最简单可靠的方案,慢了再按基准测试优化。
)
