企业官网建设流程全解析

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.md（hints 文档）中被进一步拆解为三条递进提示：

1. 暴力做法是把每个元素都当作序列起点，复杂度为 O(n²)，需要寻找更优方案；
2. 识别"序列起点"：在[1, 2, 3, 10, 11, 12]中，只有1和10是序列起点，应只对这些数尝试延伸；
3. 判断起点的方式是检查num - 1是否存在于数组中，配合哈希集合实现 O(1) 查找。

二、问题定义与思路总览

题目：给定一个未排序的整数数组nums，返回数字连续的最长序列（不要求序列元素在原数组中的位置连续）的长度。算法时间复杂度要求为 O(n)。

示例：nums = [100, 4, 200, 1, 3, 2]，最长连续序列是[1, 2, 3, 4]，答案为4。

四种解法的时间复杂度演进如下：

三、方法一：暴力法（Brute Force）

直觉（Intuition）

连续序列的本质是"下一个数（num + 1、num + 2……）是否存在"。暴力法从列表中的每一个数出发，反复检查下一个数是否存在，不断拉长连续片段，直到序列断裂。虽然方法可行，但由于大量序列被重复计算，存在大量无效工作。

算法步骤

1. 将输入列表转换为集合（Set），实现 O(1) 查找；
2. 初始化res保存最长连续段长度；
3. 遍历原列表中的每个num：
   • 新开一个长度为 0 的连续段，令curr = num；
   • 只要curr存在于集合中：连续段长度加 1，curr += 1继续检查下一个数；
   • 用res记录当前为止的最长连续段；
4. 全部检查完后返回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 res

public class Solution { public int longestConsecutive(int[] nums) { int res = 0; Set<Integer> 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(vector<int>& nums) { int res = 0; unordered_set<int> 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; HashSet<int> store = new HashSet<int>(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: Vec<i32>) -> i32 { let mut res = 0; let store: HashSet<i32> = 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）

先排序，则所有连续值会紧挨在一起。只需线性扫描已排序列表，统计每个连续段的长度：当前数字等于"期望的下一个值"时延续计数，重复值直接跳过（不影响结果），遇到断档则重置计数。相比暴力法更简单、更有条理，但受限于排序本身的复杂度。

算法步骤

1. 输入为空时直接返回0；
2. 将数组按非递减顺序排序；
3. 初始化：res（最长段）、curr（当前期望值，取nums[0]）、streak = 0、下标i = 0；
4. 在数组范围内循环：
   • 若nums[i]不等于期望值curr，说明断档：重置curr = nums[i]、streak = 0；
   • 跳过所有与curr相等的重复值（while nums[i] == curr时i++）；
   • 找到期望值后streak += 1，curr += 1更新下一个期望值；
   • 用res更新最长段；
5. 扫描完成后返回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 res

public 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(vector<int>& 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: Vec<i32>) -> 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不在集合中。这样每条连续序列恰好被完整统计一次，且每个数只参与一次计数，效率高且代码简洁。

算法步骤

1. 将列表转换为集合numSet，用于 O(1) 查找；
2. 初始化longest = 0记录最长序列长度；
3. 遍历numSet中的每个数num：
   • 若num - 1不在集合中，则num是某条序列的起点：
     • 初始化length = 1；
     • 只要num + length在集合中，就length += 1继续延伸；
   • 用longest记录最大长度；
4. 扫描结束后返回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 longest

public class Solution { public int longestConsecutive(int[] nums) { Set<Integer> 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(vector<int>& nums) { unordered_set<int> 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) { HashSet<int> numSet = new HashSet<int>(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[num+length]; 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: Vec<i32>) -> i32 { let num_set: HashSet<i32> = 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)，避免了重复扫描。

算法步骤

1. 建立哈希表mp，在边界位置存储序列长度；
2. 初始化res = 0记录最长序列；
3. 遍历输入中的每个数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维护最长序列长度；
4. 处理完所有数后返回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 res

public class Solution { public int longestConsecutive(int[] nums) { Map<Integer, 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(vector<int>& nums) { unordered_map<int, 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) { Dictionary<int, int> mp = new Dictionary<int, 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 = HashMap<Int, 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: Vec<i32>) -> i32 { let mut mp: HashMap<i32, 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 Pitfalls）

1. 从每一个数都开始计序列

最常见的低效写法是从数组中每个数都启动一次计数，导致 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 longest

C++ 版本（cpp/0128-longest-consecutive-sequence.cpp）在注释中直接标注了核心策略："Store in hash set, only check for longer seq if it's 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直接返回1；Swift 版（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