企业官网建设流程全解析

给定一个未排序的整数数组nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

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

为什么用哈希集合:这道题的核心操作只有一个——判断某个数存不存在。只需要"键",不需要任何"值",所以用 set 而不是 map。哈希集合能 O(1) 回答存在性,还自动去重,正好满足 O(n) 的要求。
思路:把全部数字放进集合。遍历每个数 x,若 x-1 也在集合里,说明 x 不是起点,跳过;若 x-1 不在,说明 x 是起点,就往后枚举 x+1、x+2…,终点减起点得到长度,更新答案。

class Solution { public: int longestConsecutive(vector<int>& nums) { // 全部入集合,自动去重,O(1)查存在 unordered_set<int> st(nums.begin(),nums.end()); int ans=0; for(auto x:st) // 遍历集合中每个数 { if(st.contains(x-1))continue; // x-1存在,说明x不是起点,跳过 int y=x+1; // x是起点,从x+1开始往后枚举 while(st.contains(y))y++; // 找到第一个不存在的数y ans=max(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) 额外空间,排序可以原地。原则是先用最简单可靠的方案,慢了再按基准测试优化。