一、题目描述给定一个未排序的整数数组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 10^5-10^9 nums[i] 10^9二、题目分析本题核心是找到最长连续序列的长度。方法一排序法O(n log n)先对数组排序遍历数组统计连续数字的长度遇到重复元素跳过遇到不连续元素更新最大长度优点实现简单缺点时间复杂度 O(n log n)不满足题目要求的 O(n)方法二哈希表法O(n)将数组所有元素存入哈希集合方便 O(1) 查询遍历数组只从每个序列的起点开始扩展序列序列起点num-1不在集合中不断查找num1, num2...统计长度更新最大长度优点每个元素最多访问一次时间复杂度 O(n)三、C语言实现1. 排序法简单易懂适合 CSDN初学者#include stdio.h #include stdlib.h int cmp(const void* a, const void* b){ return (*(int*)a - *(int*)b); } int longestConsecutive(int* nums, int numsSize) { if(numsSize 0) return 0; qsort(nums, numsSize, sizeof(int), cmp); int maxLen 1; int curLen 1; for(int i 1; i numsSize; i){ if(nums[i] nums[i-1]) continue; // 跳过重复 if(nums[i] nums[i-1] 1){ curLen; }else{ if(curLen maxLen) maxLen curLen; curLen 1; } } if(curLen maxLen) maxLen curLen; return maxLen; } // 测试 int main() { int nums[] {100,4,200,1,3,2}; int size sizeof(nums)/sizeof(nums[0]); printf(最长连续序列长度: %d\n, longestConsecutive(nums, size)); return 0; }2. 哈希表法真正 O(n)如果在 C 语言环境不支持现成哈希库可以自己实现简单哈希表或用布隆过滤器模拟面试时通常允许使用unordered_set或set思路。核心逻辑for each num in nums: if (num-1 not in set) // 是起点 len 1 while (numlen in set) len maxLen max(maxLen, len)这部分代码面试中写 Python/C 时非常高效C 语言实现可以自己用数组链表模拟哈希表。四、算法复杂度分析方法时间复杂度空间复杂度排序法O(n log n)O(1)哈希表法O(n)O(n)五、总结排序法实现简单易懂适合快速上手哈希表法真正 O(n)面试更加优雅核心技巧只从连续序列起点开始扩展✅标签C语言、哈希表、排序、LeetCode、算法题解