 哈希优化)
LeetCode 128 最长连续序列Longest Consecutive Sequence四种解法全解析从暴力到 O(n) 哈希优化【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文以 articles/longest-consecutive-sequence.md 为骨架完整讲解 LeetCode 128「最长连续序列」的四类解法暴力枚举、排序扫描、哈希集合、哈希表边界合并。题目要求在O(n) 时间复杂度内从无序数组中找出最长连续数字序列的长度如[100,4,200,1,3,2]的最长连续序列为[1,2,3,4]长度为 4。除逐语言给出可直接运行的代码外本文还结合仓库内0128-longest-consecutive-sequence.*系列源码补充实现变体Union-Find 并查集方案、提前终止优化、空数组边界处理与复杂度对比表帮助读者彻底掌握这道高频面试题的解法演进路径。一、前置知识Prerequisites在动手解题前需要具备以下三项基础能力Hash Set哈希集合提供 O(1) 平均时间复杂度的查找与成员判断是高效检测连续序列的核心数据结构Hash Map哈希表用于存储并更新序列两端边界的长度实现类似并查集的合并相邻序列思路Sorting排序理解排序如何将连续数字聚拢在一起从而用一次线性扫描统计最长段。这三项前置知识对应的方法论在仓库hints/longest-consecutive-sequence.mdhints 文档中被进一步拆解为三条递进提示暴力做法是把每个元素都当作序列起点复杂度为 O(n²)需要寻找更优方案识别序列起点在[1, 2, 3, 10, 11, 12]中只有1和10是序列起点应只对这些数尝试延伸判断起点的方式是检查num - 1是否存在于数组中配合哈希集合实现 O(1) 查找。二、问题定义与思路总览题目给定一个未排序的整数数组nums返回数字连续的最长序列不要求序列元素在原数组中的位置连续的长度。算法时间复杂度要求为 O(n)。示例nums [100, 4, 200, 1, 3, 2]最长连续序列是[1, 2, 3, 4]答案为4。四种解法的时间复杂度演进如下解法核心思想时间复杂度空间复杂度暴力法Brute Force从每个数出发向后延伸O(n²)O(n)排序法Sorting排序后单次扫描O(n log n)O(1) 或 O(n)取决于排序实现哈希集合法Hash Set仅从序列起点开始计数O(n)O(n)哈希表法Hash Map维护边界长度并合并相邻序列O(n)O(n)三、方法一暴力法Brute Force直觉Intuition连续序列的本质是下一个数num 1、num 2……是否存在。暴力法从列表中的每一个数出发反复检查下一个数是否存在不断拉长连续片段直到序列断裂。虽然方法可行但由于大量序列被重复计算存在大量无效工作。算法步骤将输入列表转换为集合Set实现 O(1) 查找初始化res保存最长连续段长度遍历原列表中的每个num新开一个长度为 0 的连续段令curr num只要curr存在于集合中连续段长度加 1curr 1继续检查下一个数用res记录当前为止的最长连续段全部检查完后返回res。多语言实现class Solution: def longestConsecutive(self, nums: List[int]) - int: res 0 store set(nums) for num in nums: streak, curr 0, num while curr in store: streak 1 curr 1 res max(res, streak) return respublic class Solution { public int longestConsecutive(int[] nums) { int res 0; SetInteger store new HashSet(); for (int num : nums) { store.add(num); } for (int num : nums) { int streak 0, curr num; while (store.contains(curr)) { streak; curr; } res Math.max(res, streak); } return res; } }class Solution { public: int longestConsecutive(vectorint nums) { int res 0; unordered_setint store(nums.begin(), nums.end()); for (int num : nums) { int streak 0, curr num; while (store.find(curr) ! store.end()) { streak; curr; } res max(res, streak); } return res; } };class Solution { /** * param {number[]} nums * return {number} */ longestConsecutive(nums) { let res 0; const store new Set(nums); for (let num of nums) { let streak 0, curr num; while (store.has(curr)) { streak; curr; } res Math.max(res, streak); } return res; } }public class Solution { public int LongestConsecutive(int[] nums) { int res 0; HashSetint store new HashSetint(nums); foreach (int num in nums) { int streak 0, curr num; while (store.Contains(curr)) { streak; curr; } res Math.Max(res, streak); } return res; } }func longestConsecutive(nums []int) int { res : 0 store : make(map[int]struct{}) for _, num : range nums { store[num] struct{}{} } for _, num : range nums { streak, curr : 0, num for _, ok : store[curr]; ok; _, ok store[curr] { streak curr } if streak res { res streak } } return res }class Solution { fun longestConsecutive(nums: IntArray): Int { var res 0 val store nums.toSet() for (num in nums) { var streak 0 var curr num while (curr in store) { streak curr } res maxOf(res, streak) } return res } }class Solution { func longestConsecutive(_ nums: [Int]) - Int { var res 0 let store Set(nums) for num in nums { var streak 0 var curr num while store.contains(curr) { streak 1 curr 1 } res max(res, streak) } return res } }impl Solution { pub fn longest_consecutive(nums: Veci32) - i32 { let mut res 0; let store: HashSeti32 nums.iter().cloned().collect(); for num in nums { let mut streak 0; let mut curr num; while store.contains(curr) { streak 1; curr 1; } res res.max(streak); } res } }复杂度分析时间复杂度O(n²)每个数都可能向后延伸出 O(n) 长度的序列空间复杂度O(n)哈希集合存储全部元素。四、方法二排序法Sorting直觉Intuition先排序则所有连续值会紧挨在一起。只需线性扫描已排序列表统计每个连续段的长度当前数字等于期望的下一个值时延续计数重复值直接跳过不影响结果遇到断档则重置计数。相比暴力法更简单、更有条理但受限于排序本身的复杂度。算法步骤输入为空时直接返回0将数组按非递减顺序排序初始化res最长段、curr当前期望值取nums[0]、streak 0、下标i 0在数组范围内循环若nums[i]不等于期望值curr说明断档重置curr nums[i]、streak 0跳过所有与curr相等的重复值while nums[i] curr时i找到期望值后streak 1curr 1更新下一个期望值用res更新最长段扫描完成后返回res。多语言实现class Solution: def longestConsecutive(self, nums: List[int]) - int: if not nums: return 0 res 0 nums.sort() curr, streak nums[0], 0 i 0 while i len(nums): if curr ! nums[i]: curr nums[i] streak 0 while i len(nums) and nums[i] curr: i 1 streak 1 curr 1 res max(res, streak) return respublic class Solution { public int longestConsecutive(int[] nums) { if (nums.length 0) { return 0; } Arrays.sort(nums); int res 0, curr nums[0], streak 0, i 0; while (i nums.length) { if (curr ! nums[i]) { curr nums[i]; streak 0; } while (i nums.length nums[i] curr) { i; } streak; curr; res Math.max(res, streak); } return res; } }class Solution { public: int longestConsecutive(vectorint nums) { if (nums.empty()) return 0; sort(nums.begin(), nums.end()); int res 0, curr nums[0], streak 0, i 0; while (i nums.size()) { if (curr ! nums[i]) { curr nums[i]; streak 0; } while (i nums.size() nums[i] curr) { i; } streak; curr; res max(res, streak); } return res; } };class Solution { /** * param {number[]} nums * return {number} */ longestConsecutive(nums) { if (nums.length 0) { return 0; } nums.sort((a, b) a - b); let res 0, curr nums[0], streak 0, i 0; while (i nums.length) { if (curr ! nums[i]) { curr nums[i]; streak 0; } while (i nums.length nums[i] curr) { i; } streak; curr; res Math.max(res, streak); } return res; } }public class Solution { public int LongestConsecutive(int[] nums) { if (nums.Length 0) { return 0; } Array.Sort(nums); int res 0, curr nums[0], streak 0, i 0; while (i nums.Length) { if (curr ! nums[i]) { curr nums[i]; streak 0; } while (i nums.Length nums[i] curr) { i; } streak; curr; res Math.Max(res, streak); } return res; } }func longestConsecutive(nums []int) int { if len(nums) 0 { return 0 } sort.Ints(nums) res : 0 curr, streak : nums[0], 0 i : 0 for i len(nums) { if curr ! nums[i] { curr nums[i] streak 0 } for i len(nums) nums[i] curr { i } streak curr if streak res { res streak } } return res }class Solution { fun longestConsecutive(nums: IntArray): Int { if (nums.isEmpty()) return 0 nums.sort() var res 0 var curr nums[0] var streak 0 var i 0 while (i nums.size) { if (curr ! nums[i]) { curr nums[i] streak 0 } while (i nums.size nums[i] curr) { i } streak curr res maxOf(res, streak) } return res } }class Solution { func longestConsecutive(_ nums: [Int]) - Int { if nums.isEmpty { return 0 } var res 0 var nums nums.sorted() var curr nums[0] var streak 0 var i 0 while i nums.count { if curr ! nums[i] { curr nums[i] streak 0 } while i nums.count nums[i] curr { i 1 } streak 1 curr 1 res max(res, streak) } return res } }impl Solution { pub fn longest_consecutive(nums: Veci32) - i32 { if nums.is_empty() { return 0; } let mut nums nums; nums.sort(); let mut res 0; let mut curr nums[0]; let mut streak 0; let mut i 0; while i nums.len() { if curr ! nums[i] { curr nums[i]; streak 0; } while i nums.len() nums[i] curr { i 1; } streak 1; curr 1; res res.max(streak); } res } }复杂度分析时间复杂度O(n log n)排序主导空间复杂度O(1) 或 O(n)取决于所用排序算法的实现。五、方法三哈希集合法Hash Set—— 最优解直觉Intuition为避免重复统计同一序列只在找到连续序列起点时才计数。一个数是序列起点的充要条件是num - 1不在集合中。这样每条连续序列恰好被完整统计一次且每个数只参与一次计数效率高且代码简洁。算法步骤将列表转换为集合numSet用于 O(1) 查找初始化longest 0记录最长序列长度遍历numSet中的每个数num若num - 1不在集合中则num是某条序列的起点初始化length 1只要num length在集合中就length 1继续延伸用longest记录最大长度扫描结束后返回longest。多语言实现class Solution: def longestConsecutive(self, nums: List[int]) - int: numSet set(nums) longest 0 for num in numSet: if (num - 1) not in numSet: length 1 while (num length) in numSet: length 1 longest max(length, longest) return longestpublic class Solution { public int longestConsecutive(int[] nums) { SetInteger numSet new HashSet(); for (int num : nums) { numSet.add(num); } int longest 0; for (int num : numSet) { if (!numSet.contains(num - 1)) { int length 1; while (numSet.contains(num length)) { length; } longest Math.max(longest, length); } } return longest; } }class Solution { public: int longestConsecutive(vectorint nums) { unordered_setint numSet(nums.begin(), nums.end()); int longest 0; for (int num : numSet) { if (numSet.find(num - 1) numSet.end()) { int length 1; while (numSet.find(num length) ! numSet.end()) { length; } longest max(longest, length); } } return longest; } };class Solution { /** * param {number[]} nums * return {number} */ longestConsecutive(nums) { const numSet new Set(nums); let longest 0; for (let num of numSet) { if (!numSet.has(num - 1)) { let length 1; while (numSet.has(num length)) { length; } longest Math.max(longest, length); } } return longest; } }public class Solution { public int LongestConsecutive(int[] nums) { HashSetint numSet new HashSetint(nums); int longest 0; foreach (int num in numSet) { if (!numSet.Contains(num - 1)) { int length 1; while (numSet.Contains(num length)) { length; } longest Math.Max(longest, length); } } return longest; } }func longestConsecutive(nums []int) int { numSet : make(map[int]struct{}) for _, num : range nums { numSet[num] struct{}{} } longest : 0 for num : range numSet { if _, found : numSet[num-1]; !found { length : 1 for { if _, exists : numSet[numlength]; exists { length } else { break } } if length longest { longest length } } } return longest }class Solution { fun longestConsecutive(nums: IntArray): Int { val numSet nums.toSet() var longest 0 for (num in numSet) { if ((num - 1) !in numSet) { var length 1 while ((num length) in numSet) { length } longest maxOf(longest, length) } } return longest } }class Solution { func longestConsecutive(_ nums: [Int]) - Int { let numSet Set(nums) var longest 0 for num in numSet { if !numSet.contains(num - 1) { var length 1 while numSet.contains(num length) { length 1 } longest max(length, longest) } } return longest } }impl Solution { pub fn longest_consecutive(nums: Veci32) - i32 { let num_set: HashSeti32 nums.iter().cloned().collect(); let mut longest 0; for num in num_set { if !num_set.contains((num - 1)) { let mut length 1; while num_set.contains((num length)) { length 1; } longest longest.max(length); } } longest } }复杂度分析时间复杂度O(n)每个数至多作为起点被遍历一次while 循环累计次数不超过 n空间复杂度O(n)。六、方法四哈希表法Hash Map—— 边界合并直觉Intuition把每个新数字放入哈希表时它可能连接左右两条已有序列或延伸其中一条。我们只需读取邻居处记录的长度mp[num - 1]紧邻num之前结束的序列长度mp[num 1]紧邻num之后开始的序列长度。将两者相加再加 1当前数字本身即得到合并后的总长度随后更新该序列的左边界与右边界以便后续查询。整条链路的操作都保持 O(1)避免了重复扫描。算法步骤建立哈希表mp在边界位置存储序列长度初始化res 0记录最长序列遍历输入中的每个数num若num已存在于mp跳过计算新序列长度length mp[num - 1] mp[num 1] 1将length存到mp[num]更新边界左边界mp[num - mp[num - 1]] length右边界mp[num mp[num 1]] length用res维护最长序列长度处理完所有数后返回res。多语言实现class Solution: def longestConsecutive(self, nums: List[int]) - int: mp defaultdict(int) res 0 for num in nums: if not mp[num]: mp[num] mp[num - 1] mp[num 1] 1 mp[num - mp[num - 1]] mp[num] mp[num mp[num 1]] mp[num] res max(res, mp[num]) return respublic class Solution { public int longestConsecutive(int[] nums) { MapInteger, Integer mp new HashMap(); int res 0; for (int num : nums) { if (!mp.containsKey(num)) { mp.put(num, mp.getOrDefault(num - 1, 0) mp.getOrDefault(num 1, 0) 1); mp.put(num - mp.getOrDefault(num - 1, 0), mp.get(num)); mp.put(num mp.getOrDefault(num 1, 0), mp.get(num)); res Math.max(res, mp.get(num)); } } return res; } }class Solution { public: int longestConsecutive(vectorint nums) { unordered_mapint, int mp; int res 0; for (int num : nums) { if (!mp[num]) { mp[num] mp[num - 1] mp[num 1] 1; mp[num - mp[num - 1]] mp[num]; mp[num mp[num 1]] mp[num]; res max(res, mp[num]); } } return res; } };class Solution { /** * param {number[]} nums * return {number} */ longestConsecutive(nums) { const mp new Map(); let res 0; for (let num of nums) { if (!mp.has(num)) { mp.set( num, (mp.get(num - 1) || 0) (mp.get(num 1) || 0) 1, ); mp.set(num - (mp.get(num - 1) || 0), mp.get(num)); mp.set(num (mp.get(num 1) || 0), mp.get(num)); res Math.max(res, mp.get(num)); } } return res; } }public class Solution { public int LongestConsecutive(int[] nums) { Dictionaryint, int mp new Dictionaryint, int(); int res 0; foreach (int num in nums) { if (!mp.ContainsKey(num)) { mp[num] (mp.ContainsKey(num - 1) ? mp[num - 1] : 0) (mp.ContainsKey(num 1) ? mp[num 1] : 0) 1; mp[num - (mp.ContainsKey(num - 1) ? mp[num - 1] : 0)] mp[num]; mp[num (mp.ContainsKey(num 1) ? mp[num 1] : 0)] mp[num]; res Math.Max(res, mp[num]); } } return res; } }func longestConsecutive(nums []int) int { mp : make(map[int]int) res : 0 for _, num : range nums { if mp[num] 0 { left : mp[num - 1] right : mp[num 1] sum : left right 1 mp[num] sum mp[num - left] sum mp[num right] sum if sum res { res sum } } } return res }class Solution { fun longestConsecutive(nums: IntArray): Int { val mp HashMapInt, Int() var res 0 for (num in nums) { if (mp[num] null) { val left mp[num - 1] ?: 0 val right mp[num 1] ?: 0 val sum left right 1 mp[num] sum mp[num - left] sum mp[num right] sum res maxOf(res, sum) } } return res } }class Solution { func longestConsecutive(_ nums: [Int]) - Int { var mp [Int: Int]() var res 0 for num in nums { if mp[num] nil { let left mp[num - 1] ?? 0 let right mp[num 1] ?? 0 let length left right 1 mp[num] length mp[num - left] length mp[num right] length res max(res, length) } } return res } }impl Solution { pub fn longest_consecutive(nums: Veci32) - i32 { let mut mp: HashMapi32, i32 HashMap::new(); let mut res 0; for num in nums { if !mp.contains_key(num) { let left *mp.get((num - 1)).unwrap_or(0); let right *mp.get((num 1)).unwrap_or(0); let length left right 1; mp.insert(num, length); mp.insert(num - left, length); mp.insert(num right, length); res res.max(length); } } res } }复杂度分析时间复杂度O(n)空间复杂度O(n)。七、常见陷阱Common Pitfalls1. 从每一个数都开始计序列最常见的低效写法是从数组中每个数都启动一次计数导致 O(n²) 复杂度。关键优化是只从序列起点开始计数即仅当num - 1不在集合中时才启动从而保证每条序列只被统计一次。2. 重复值处理不当输入数组可能包含重复元素。使用集合可以自动去重但若遍历的是原数组而非集合同一个序列可能被重复处理多次造成无效计算。3. 忘记处理空输入输入数组为空时最长连续序列长度为0。一些默认至少有一个元素的实现会在此边界情况下出错或返回错误结果。八、仓库源码纵深多语言实现与变体1. 最优解在仓库中的落地仓库在python/0128-longest-consecutive-sequence.py、cpp/0128-longest-consecutive-sequence.cpp、go/0128-longest-consecutive-sequence.go、rust/0128-longest-consecutive-sequence.rs、typescript/0128-longest-consecutive-sequence.ts、swift/0128-longest-consecutive-sequence.swift、ruby/0128-longest-consecutive-sequence.rb及c、java、javascript、kotlin、csharp等目录下均提供了本题的解法。其中 Python 实现python/0128-longest-consecutive-sequence.py与本文第五节的哈希集合最优解完全一致class Solution: def longestConsecutive(self, nums: List[int]) - int: numSet set(nums) longest 0 for n in numSet: # check if its the start of a sequence if (n - 1) not in numSet: length 1 while (n length) in numSet: length 1 longest max(length, longest) return longestC 版本cpp/0128-longest-consecutive-sequence.cpp在注释中直接标注了核心策略Store in hash set, only check for longer seq if its the beginning并注明Time: O(n)、Space: O(n)与本文分析一致。2. 实现变体一提前终止剪枝Java 实现java/0128-longest-consecutive-sequence.java在最优解基础上增加了剪枝当longest nums.length / 2时提前break。其含义是——一旦最长连续段已经超过数组长度的一半就不可能再出现更长的序列另一条序列若更长则总元素数将超过 n因此可以安全终止循环属于工程上的微优化if (longest nums.length / 2) break;3. 实现变体二Union-Find 并查集方案Kotlin 源码kotlin/0128-longest-consecutive-sequence.kt在哈希集合解法之外额外附赠了并查集DSU替代方案用parent数组与size数组维护相邻数字属于同一连通块处理每个数字时将其与num - 1、num 1所在块union合并最终遍历根节点统计最大块大小。该方案在概念上与第六节的哈希表边界合并法同源均体现了合并相邻区间的核心思想适合在面试中作为进阶扩展思路展示。4. 空输入与单元素边界仓库中多个实现显式处理了边界情况Java 版以if (nums.length 0) return 0兜底Kotlin 版额外处理nums.size 1直接返回1Swift 版swift/0128-longest-consecutive-sequence.swift通过注释明确remove duplicates numbers说明去重是集合化处理的首要目的。这些写法与第七节常见陷阱中强调的空输入、重复值问题一一对应可作为工程落地的参考。九、总结四种解法呈清晰的演进脉络暴力法用集合支持 O(1) 查找但重复计数排序法利用有序性简化扫描但受限于 O(n log n)哈希集合法通过只从起点计数达到 O(n)哈希表边界合并法则以边界长度维护 区间合并的思想同样达到 O(n)。面试与刷题场景下哈希集合法是最推荐的答案——代码最短、思路最直观、严格满足题目的 O(n) 要求若想展示更深的功底可补充哈希表合并或并查集变体。仓库内 12 种语言的0128-longest-consecutive-sequence.*实现及 hints 文档 提供了完整的对照素材便于按语言快速查阅与练习。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode 128 最长连续序列（Longest Consecutive Sequence）四种解法全解析：从暴力到 O(n) 哈希优化
LeetCode 128 最长连续序列Longest Consecutive Sequence四种解法全解析从暴力到 O(n) 哈希优化【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文以 articles/longest-consecutive-sequence.md 为骨架完整讲解 LeetCode 128「最长连续序列」的四类解法暴力枚举、排序扫描、哈希集合、哈希表边界合并。题目要求在O(n) 时间复杂度内从无序数组中找出最长连续数字序列的长度如[100,4,200,1,3,2]的最长连续序列为[1,2,3,4]长度为 4。除逐语言给出可直接运行的代码外本文还结合仓库内0128-longest-consecutive-sequence.*系列源码补充实现变体Union-Find 并查集方案、提前终止优化、空数组边界处理与复杂度对比表帮助读者彻底掌握这道高频面试题的解法演进路径。一、前置知识Prerequisites在动手解题前需要具备以下三项基础能力Hash Set哈希集合提供 O(1) 平均时间复杂度的查找与成员判断是高效检测连续序列的核心数据结构Hash Map哈希表用于存储并更新序列两端边界的长度实现类似并查集的合并相邻序列思路Sorting排序理解排序如何将连续数字聚拢在一起从而用一次线性扫描统计最长段。这三项前置知识对应的方法论在仓库hints/longest-consecutive-sequence.mdhints 文档中被进一步拆解为三条递进提示暴力做法是把每个元素都当作序列起点复杂度为 O(n²)需要寻找更优方案识别序列起点在[1, 2, 3, 10, 11, 12]中只有1和10是序列起点应只对这些数尝试延伸判断起点的方式是检查num - 1是否存在于数组中配合哈希集合实现 O(1) 查找。二、问题定义与思路总览题目给定一个未排序的整数数组nums返回数字连续的最长序列不要求序列元素在原数组中的位置连续的长度。算法时间复杂度要求为 O(n)。示例nums [100, 4, 200, 1, 3, 2]最长连续序列是[1, 2, 3, 4]答案为4。四种解法的时间复杂度演进如下解法核心思想时间复杂度空间复杂度暴力法Brute Force从每个数出发向后延伸O(n²)O(n)排序法Sorting排序后单次扫描O(n log n)O(1) 或 O(n)取决于排序实现哈希集合法Hash Set仅从序列起点开始计数O(n)O(n)哈希表法Hash Map维护边界长度并合并相邻序列O(n)O(n)三、方法一暴力法Brute Force直觉Intuition连续序列的本质是下一个数num 1、num 2……是否存在。暴力法从列表中的每一个数出发反复检查下一个数是否存在不断拉长连续片段直到序列断裂。虽然方法可行但由于大量序列被重复计算存在大量无效工作。算法步骤将输入列表转换为集合Set实现 O(1) 查找初始化res保存最长连续段长度遍历原列表中的每个num新开一个长度为 0 的连续段令curr num只要curr存在于集合中连续段长度加 1curr 1继续检查下一个数用res记录当前为止的最长连续段全部检查完后返回res。多语言实现class Solution: def longestConsecutive(self, nums: List[int]) - int: res 0 store set(nums) for num in nums: streak, curr 0, num while curr in store: streak 1 curr 1 res max(res, streak) return respublic class Solution { public int longestConsecutive(int[] nums) { int res 0; SetInteger store new HashSet(); for (int num : nums) { store.add(num); } for (int num : nums) { int streak 0, curr num; while (store.contains(curr)) { streak; curr; } res Math.max(res, streak); } return res; } }class Solution { public: int longestConsecutive(vectorint nums) { int res 0; unordered_setint store(nums.begin(), nums.end()); for (int num : nums) { int streak 0, curr num; while (store.find(curr) ! store.end()) { streak; curr; } res max(res, streak); } return res; } };class Solution { /** * param {number[]} nums * return {number} */ longestConsecutive(nums) { let res 0; const store new Set(nums); for (let num of nums) { let streak 0, curr num; while (store.has(curr)) { streak; curr; } res Math.max(res, streak); } return res; } }public class Solution { public int LongestConsecutive(int[] nums) { int res 0; HashSetint store new HashSetint(nums); foreach (int num in nums) { int streak 0, curr num; while (store.Contains(curr)) { streak; curr; } res Math.Max(res, streak); } return res; } }func longestConsecutive(nums []int) int { res : 0 store : make(map[int]struct{}) for _, num : range nums { store[num] struct{}{} } for _, num : range nums { streak, curr : 0, num for _, ok : store[curr]; ok; _, ok store[curr] { streak curr } if streak res { res streak } } return res }class Solution { fun longestConsecutive(nums: IntArray): Int { var res 0 val store nums.toSet() for (num in nums) { var streak 0 var curr num while (curr in store) { streak curr } res maxOf(res, streak) } return res } }class Solution { func longestConsecutive(_ nums: [Int]) - Int { var res 0 let store Set(nums) for num in nums { var streak 0 var curr num while store.contains(curr) { streak 1 curr 1 } res max(res, streak) } return res } }impl Solution { pub fn longest_consecutive(nums: Veci32) - i32 { let mut res 0; let store: HashSeti32 nums.iter().cloned().collect(); for num in nums { let mut streak 0; let mut curr num; while store.contains(curr) { streak 1; curr 1; } res res.max(streak); } res } }复杂度分析时间复杂度O(n²)每个数都可能向后延伸出 O(n) 长度的序列空间复杂度O(n)哈希集合存储全部元素。四、方法二排序法Sorting直觉Intuition先排序则所有连续值会紧挨在一起。只需线性扫描已排序列表统计每个连续段的长度当前数字等于期望的下一个值时延续计数重复值直接跳过不影响结果遇到断档则重置计数。相比暴力法更简单、更有条理但受限于排序本身的复杂度。算法步骤输入为空时直接返回0将数组按非递减顺序排序初始化res最长段、curr当前期望值取nums[0]、streak 0、下标i 0在数组范围内循环若nums[i]不等于期望值curr说明断档重置curr nums[i]、streak 0跳过所有与curr相等的重复值while nums[i] curr时i找到期望值后streak 1curr 1更新下一个期望值用res更新最长段扫描完成后返回res。多语言实现class Solution: def longestConsecutive(self, nums: List[int]) - int: if not nums: return 0 res 0 nums.sort() curr, streak nums[0], 0 i 0 while i len(nums): if curr ! nums[i]: curr nums[i] streak 0 while i len(nums) and nums[i] curr: i 1 streak 1 curr 1 res max(res, streak) return respublic class Solution { public int longestConsecutive(int[] nums) { if (nums.length 0) { return 0; } Arrays.sort(nums); int res 0, curr nums[0], streak 0, i 0; while (i nums.length) { if (curr ! nums[i]) { curr nums[i]; streak 0; } while (i nums.length nums[i] curr) { i; } streak; curr; res Math.max(res, streak); } return res; } }class Solution { public: int longestConsecutive(vectorint nums) { if (nums.empty()) return 0; sort(nums.begin(), nums.end()); int res 0, curr nums[0], streak 0, i 0; while (i nums.size()) { if (curr ! nums[i]) { curr nums[i]; streak 0; } while (i nums.size() nums[i] curr) { i; } streak; curr; res max(res, streak); } return res; } };class Solution { /** * param {number[]} nums * return {number} */ longestConsecutive(nums) { if (nums.length 0) { return 0; } nums.sort((a, b) a - b); let res 0, curr nums[0], streak 0, i 0; while (i nums.length) { if (curr ! nums[i]) { curr nums[i]; streak 0; } while (i nums.length nums[i] curr) { i; } streak; curr; res Math.max(res, streak); } return res; } }public class Solution { public int LongestConsecutive(int[] nums) { if (nums.Length 0) { return 0; } Array.Sort(nums); int res 0, curr nums[0], streak 0, i 0; while (i nums.Length) { if (curr ! nums[i]) { curr nums[i]; streak 0; } while (i nums.Length nums[i] curr) { i; } streak; curr; res Math.Max(res, streak); } return res; } }func longestConsecutive(nums []int) int { if len(nums) 0 { return 0 } sort.Ints(nums) res : 0 curr, streak : nums[0], 0 i : 0 for i len(nums) { if curr ! nums[i] { curr nums[i] streak 0 } for i len(nums) nums[i] curr { i } streak curr if streak res { res streak } } return res }class Solution { fun longestConsecutive(nums: IntArray): Int { if (nums.isEmpty()) return 0 nums.sort() var res 0 var curr nums[0] var streak 0 var i 0 while (i nums.size) { if (curr ! nums[i]) { curr nums[i] streak 0 } while (i nums.size nums[i] curr) { i } streak curr res maxOf(res, streak) } return res } }class Solution { func longestConsecutive(_ nums: [Int]) - Int { if nums.isEmpty { return 0 } var res 0 var nums nums.sorted() var curr nums[0] var streak 0 var i 0 while i nums.count { if curr ! nums[i] { curr nums[i] streak 0 } while i nums.count nums[i] curr { i 1 } streak 1 curr 1 res max(res, streak) } return res } }impl Solution { pub fn longest_consecutive(nums: Veci32) - i32 { if nums.is_empty() { return 0; } let mut nums nums; nums.sort(); let mut res 0; let mut curr nums[0]; let mut streak 0; let mut i 0; while i nums.len() { if curr ! nums[i] { curr nums[i]; streak 0; } while i nums.len() nums[i] curr { i 1; } streak 1; curr 1; res res.max(streak); } res } }复杂度分析时间复杂度O(n log n)排序主导空间复杂度O(1) 或 O(n)取决于所用排序算法的实现。五、方法三哈希集合法Hash Set—— 最优解直觉Intuition为避免重复统计同一序列只在找到连续序列起点时才计数。一个数是序列起点的充要条件是num - 1不在集合中。这样每条连续序列恰好被完整统计一次且每个数只参与一次计数效率高且代码简洁。算法步骤将列表转换为集合numSet用于 O(1) 查找初始化longest 0记录最长序列长度遍历numSet中的每个数num若num - 1不在集合中则num是某条序列的起点初始化length 1只要num length在集合中就length 1继续延伸用longest记录最大长度扫描结束后返回longest。多语言实现class Solution: def longestConsecutive(self, nums: List[int]) - int: numSet set(nums) longest 0 for num in numSet: if (num - 1) not in numSet: length 1 while (num length) in numSet: length 1 longest max(length, longest) return longestpublic class Solution { public int longestConsecutive(int[] nums) { SetInteger numSet new HashSet(); for (int num : nums) { numSet.add(num); } int longest 0; for (int num : numSet) { if (!numSet.contains(num - 1)) { int length 1; while (numSet.contains(num length)) { length; } longest Math.max(longest, length); } } return longest; } }class Solution { public: int longestConsecutive(vectorint nums) { unordered_setint numSet(nums.begin(), nums.end()); int longest 0; for (int num : numSet) { if (numSet.find(num - 1) numSet.end()) { int length 1; while (numSet.find(num length) ! numSet.end()) { length; } longest max(longest, length); } } return longest; } };class Solution { /** * param {number[]} nums * return {number} */ longestConsecutive(nums) { const numSet new Set(nums); let longest 0; for (let num of numSet) { if (!numSet.has(num - 1)) { let length 1; while (numSet.has(num length)) { length; } longest Math.max(longest, length); } } return longest; } }public class Solution { public int LongestConsecutive(int[] nums) { HashSetint numSet new HashSetint(nums); int longest 0; foreach (int num in numSet) { if (!numSet.Contains(num - 1)) { int length 1; while (numSet.Contains(num length)) { length; } longest Math.Max(longest, length); } } return longest; } }func longestConsecutive(nums []int) int { numSet : make(map[int]struct{}) for _, num : range nums { numSet[num] struct{}{} } longest : 0 for num : range numSet { if _, found : numSet[num-1]; !found { length : 1 for { if _, exists : numSet[numlength]; exists { length } else { break } } if length longest { longest length } } } return longest }class Solution { fun longestConsecutive(nums: IntArray): Int { val numSet nums.toSet() var longest 0 for (num in numSet) { if ((num - 1) !in numSet) { var length 1 while ((num length) in numSet) { length } longest maxOf(longest, length) } } return longest } }class Solution { func longestConsecutive(_ nums: [Int]) - Int { let numSet Set(nums) var longest 0 for num in numSet { if !numSet.contains(num - 1) { var length 1 while numSet.contains(num length) { length 1 } longest max(length, longest) } } return longest } }impl Solution { pub fn longest_consecutive(nums: Veci32) - i32 { let num_set: HashSeti32 nums.iter().cloned().collect(); let mut longest 0; for num in num_set { if !num_set.contains((num - 1)) { let mut length 1; while num_set.contains((num length)) { length 1; } longest longest.max(length); } } longest } }复杂度分析时间复杂度O(n)每个数至多作为起点被遍历一次while 循环累计次数不超过 n空间复杂度O(n)。六、方法四哈希表法Hash Map—— 边界合并直觉Intuition把每个新数字放入哈希表时它可能连接左右两条已有序列或延伸其中一条。我们只需读取邻居处记录的长度mp[num - 1]紧邻num之前结束的序列长度mp[num 1]紧邻num之后开始的序列长度。将两者相加再加 1当前数字本身即得到合并后的总长度随后更新该序列的左边界与右边界以便后续查询。整条链路的操作都保持 O(1)避免了重复扫描。算法步骤建立哈希表mp在边界位置存储序列长度初始化res 0记录最长序列遍历输入中的每个数num若num已存在于mp跳过计算新序列长度length mp[num - 1] mp[num 1] 1将length存到mp[num]更新边界左边界mp[num - mp[num - 1]] length右边界mp[num mp[num 1]] length用res维护最长序列长度处理完所有数后返回res。多语言实现class Solution: def longestConsecutive(self, nums: List[int]) - int: mp defaultdict(int) res 0 for num in nums: if not mp[num]: mp[num] mp[num - 1] mp[num 1] 1 mp[num - mp[num - 1]] mp[num] mp[num mp[num 1]] mp[num] res max(res, mp[num]) return respublic class Solution { public int longestConsecutive(int[] nums) { MapInteger, Integer mp new HashMap(); int res 0; for (int num : nums) { if (!mp.containsKey(num)) { mp.put(num, mp.getOrDefault(num - 1, 0) mp.getOrDefault(num 1, 0) 1); mp.put(num - mp.getOrDefault(num - 1, 0), mp.get(num)); mp.put(num mp.getOrDefault(num 1, 0), mp.get(num)); res Math.max(res, mp.get(num)); } } return res; } }class Solution { public: int longestConsecutive(vectorint nums) { unordered_mapint, int mp; int res 0; for (int num : nums) { if (!mp[num]) { mp[num] mp[num - 1] mp[num 1] 1; mp[num - mp[num - 1]] mp[num]; mp[num mp[num 1]] mp[num]; res max(res, mp[num]); } } return res; } };class Solution { /** * param {number[]} nums * return {number} */ longestConsecutive(nums) { const mp new Map(); let res 0; for (let num of nums) { if (!mp.has(num)) { mp.set( num, (mp.get(num - 1) || 0) (mp.get(num 1) || 0) 1, ); mp.set(num - (mp.get(num - 1) || 0), mp.get(num)); mp.set(num (mp.get(num 1) || 0), mp.get(num)); res Math.max(res, mp.get(num)); } } return res; } }public class Solution { public int LongestConsecutive(int[] nums) { Dictionaryint, int mp new Dictionaryint, int(); int res 0; foreach (int num in nums) { if (!mp.ContainsKey(num)) { mp[num] (mp.ContainsKey(num - 1) ? mp[num - 1] : 0) (mp.ContainsKey(num 1) ? mp[num 1] : 0) 1; mp[num - (mp.ContainsKey(num - 1) ? mp[num - 1] : 0)] mp[num]; mp[num (mp.ContainsKey(num 1) ? mp[num 1] : 0)] mp[num]; res Math.Max(res, mp[num]); } } return res; } }func longestConsecutive(nums []int) int { mp : make(map[int]int) res : 0 for _, num : range nums { if mp[num] 0 { left : mp[num - 1] right : mp[num 1] sum : left right 1 mp[num] sum mp[num - left] sum mp[num right] sum if sum res { res sum } } } return res }class Solution { fun longestConsecutive(nums: IntArray): Int { val mp HashMapInt, Int() var res 0 for (num in nums) { if (mp[num] null) { val left mp[num - 1] ?: 0 val right mp[num 1] ?: 0 val sum left right 1 mp[num] sum mp[num - left] sum mp[num right] sum res maxOf(res, sum) } } return res } }class Solution { func longestConsecutive(_ nums: [Int]) - Int { var mp [Int: Int]() var res 0 for num in nums { if mp[num] nil { let left mp[num - 1] ?? 0 let right mp[num 1] ?? 0 let length left right 1 mp[num] length mp[num - left] length mp[num right] length res max(res, length) } } return res } }impl Solution { pub fn longest_consecutive(nums: Veci32) - i32 { let mut mp: HashMapi32, i32 HashMap::new(); let mut res 0; for num in nums { if !mp.contains_key(num) { let left *mp.get((num - 1)).unwrap_or(0); let right *mp.get((num 1)).unwrap_or(0); let length left right 1; mp.insert(num, length); mp.insert(num - left, length); mp.insert(num right, length); res res.max(length); } } res } }复杂度分析时间复杂度O(n)空间复杂度O(n)。七、常见陷阱Common Pitfalls1. 从每一个数都开始计序列最常见的低效写法是从数组中每个数都启动一次计数导致 O(n²) 复杂度。关键优化是只从序列起点开始计数即仅当num - 1不在集合中时才启动从而保证每条序列只被统计一次。2. 重复值处理不当输入数组可能包含重复元素。使用集合可以自动去重但若遍历的是原数组而非集合同一个序列可能被重复处理多次造成无效计算。3. 忘记处理空输入输入数组为空时最长连续序列长度为0。一些默认至少有一个元素的实现会在此边界情况下出错或返回错误结果。八、仓库源码纵深多语言实现与变体1. 最优解在仓库中的落地仓库在python/0128-longest-consecutive-sequence.py、cpp/0128-longest-consecutive-sequence.cpp、go/0128-longest-consecutive-sequence.go、rust/0128-longest-consecutive-sequence.rs、typescript/0128-longest-consecutive-sequence.ts、swift/0128-longest-consecutive-sequence.swift、ruby/0128-longest-consecutive-sequence.rb及c、java、javascript、kotlin、csharp等目录下均提供了本题的解法。其中 Python 实现python/0128-longest-consecutive-sequence.py与本文第五节的哈希集合最优解完全一致class Solution: def longestConsecutive(self, nums: List[int]) - int: numSet set(nums) longest 0 for n in numSet: # check if its the start of a sequence if (n - 1) not in numSet: length 1 while (n length) in numSet: length 1 longest max(length, longest) return longestC 版本cpp/0128-longest-consecutive-sequence.cpp在注释中直接标注了核心策略Store in hash set, only check for longer seq if its the beginning并注明Time: O(n)、Space: O(n)与本文分析一致。2. 实现变体一提前终止剪枝Java 实现java/0128-longest-consecutive-sequence.java在最优解基础上增加了剪枝当longest nums.length / 2时提前break。其含义是——一旦最长连续段已经超过数组长度的一半就不可能再出现更长的序列另一条序列若更长则总元素数将超过 n因此可以安全终止循环属于工程上的微优化if (longest nums.length / 2) break;3. 实现变体二Union-Find 并查集方案Kotlin 源码kotlin/0128-longest-consecutive-sequence.kt在哈希集合解法之外额外附赠了并查集DSU替代方案用parent数组与size数组维护相邻数字属于同一连通块处理每个数字时将其与num - 1、num 1所在块union合并最终遍历根节点统计最大块大小。该方案在概念上与第六节的哈希表边界合并法同源均体现了合并相邻区间的核心思想适合在面试中作为进阶扩展思路展示。4. 空输入与单元素边界仓库中多个实现显式处理了边界情况Java 版以if (nums.length 0) return 0兜底Kotlin 版额外处理nums.size 1直接返回1Swift 版swift/0128-longest-consecutive-sequence.swift通过注释明确remove duplicates numbers说明去重是集合化处理的首要目的。这些写法与第七节常见陷阱中强调的空输入、重复值问题一一对应可作为工程落地的参考。九、总结四种解法呈清晰的演进脉络暴力法用集合支持 O(1) 查找但重复计数排序法利用有序性简化扫描但受限于 O(n log n)哈希集合法通过只从起点计数达到 O(n)哈希表边界合并法则以边界长度维护 区间合并的思想同样达到 O(n)。面试与刷题场景下哈希集合法是最推荐的答案——代码最短、思路最直观、严格满足题目的 O(n) 要求若想展示更深的功底可补充哈希表合并或并查集变体。仓库内 12 种语言的0128-longest-consecutive-sequence.*实现及 hints 文档 提供了完整的对照素材便于按语言快速查阅与练习。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
