企业官网建设流程全解析

• 示例工程

本文基于 doocs/leetcode 仓库中 128. 最长连续序列题解，完整梳理该题的两种线性时间哈希表算法：从「长度表拼接」到「仅从序列起点扩展」的优化演进，覆盖思路推导、Python3/Java/C++/Go/TypeScript/Rust/JavaScript 七种语言实现、复杂度证明与边界分析。读完后你将掌握如何在不排序的前提下用哈希集合在均摊 O(n) 时间内求出未排序数组中最长连续数字段的长度。

题目描述与约束

给定一个未排序的整数数组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（注意数组中存在重复元素1）。

提示（数据范围）：

为什么必须走 O(n)：复杂度分析

最直觉的做法是「先排序再扫描连续段」，时间复杂度为 O(n log n)，无法满足题目对O(n)的硬性要求。由于n最大可达10^5，哈希结构是唯一能在期望 O(1) 时间内完成「元素是否存在」判定的工具。两种解法都围绕同一个核心数据结构展开：一个存放去重后所有元素的哈希集合s，区别仅在于「如何组织扩展过程并保证总工作量是线性的」。

方法一：哈希集合 + 长度表（段拼接）

思路

思考（继承自原文档）：排序后扫连续段是 O(n log n)，题目要求 O(n)。放入哈希集合后，从每个尚未删除的x向右延伸，直到断掉，并把这段长度记在起点上，供更早的起点拼接。每个数进出集合一次。

具体做法：

1. 用哈希集合s存储数组中所有元素（自动去重）；
2. 用变量ans记录最长连续序列长度；
3. 用哈希表d记录每个元素x所在连续序列的长度；
4. 遍历数组中每个元素x，用临时变量y = x，不断尝试匹配y+1, y+2, y+3, …，直到匹配不到为止，过程中将匹配到的元素从s中移除；
5. 当前元素x所在连续序列的长度为d[x] = d[y] + y - x，并更新ans = max(ans, d[x])；
6. 遍历结束后返回ans。

这里d[y] + y - x是精髓：x向右扫到的终点是y（即[x, y-1]连续存在、y缺失），这一段长度y - x可以直接拼接到y开头的那条已有序列（长度d[y]）上，于是x开头的整段长度为d[y] + y - x。

代码实现

Python3

class Solution: def longestConsecutive(self, nums: List[int]) -> int: s = set(nums) ans = 0 d = defaultdict(int) for x in nums: y = x while y in s: s.remove(y) y += 1 d[x] = d[y] + y - x ans = max(ans, d[x]) return ans

对应仓库文件：Solution.py

Java

class Solution { public int longestConsecutive(int[] nums) { Set<Integer> s = new HashSet<>(); for (int x : nums) { s.add(x); } int ans = 0; Map<Integer, Integer> d = new HashMap<>(); for (int x : nums) { int y = x; while (s.contains(y)) { s.remove(y++); } d.put(x, d.getOrDefault(y, 0) + y - x); ans = Math.max(ans, d.get(x)); } return ans; } }

对应仓库文件：Solution.java

C++

class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> s(nums.begin(), nums.end()); int ans = 0; unordered_map<int, int> d; for (int x : nums) { int y = x; while (s.contains(y)) { s.erase(y++); } d[x] = (d.contains(y) ? d[y] : 0) + y - x; ans = max(ans, d[x]); } return ans; } };

对应仓库文件：Solution.cpp。注意s.contains(y)/d.contains(y)是 C++20 引入的接口，编译时需启用 C++20 标准。

Go

func longestConsecutive(nums []int) (ans int) { s := map[int]bool{} for _, x := range nums { s[x] = true } d := map[int]int{} for _, x := range nums { y := x for s[y] { delete(s, y) y++ } d[x] = d[y] + y - x ans = max(ans, d[x]) } return }

对应仓库文件：Solution.go。Go 版本利用「取不存在的 key 返回零值false」和 Go 1.21 引入的内置max函数，代码最为紧凑。

TypeScript

function longestConsecutive(nums: number[]): number { const s = new Set(nums); let ans = 0; const d = new Map<number, number>(); for (const x of nums) { let y = x; while (s.has(y)) { s.delete(y++); } d.set(x, (d.get(y) || 0) + (y - x)); ans = Math.max(ans, d.get(x)!); } return ans; }

对应仓库文件：Solution.ts

Rust

use std::collections::{HashMap, HashSet}; impl Solution { pub fn longest_consecutive(nums: Vec<i32>) -> i32 { let mut s: HashSet<i32> = nums.iter().cloned().collect(); let mut ans = 0; let mut d: HashMap<i32, i32> = HashMap::new(); for &x in &nums { let mut y = x; while s.contains(&y) { s.remove(&y); y += 1; } let length = d.get(&(y)).unwrap_or(&0) + y - x; d.insert(x, length); ans = ans.max(length); } ans } }

对应仓库文件：Solution.rs

JavaScript

/** * @param {number[]} nums * @return {number} */ var longestConsecutive = function (nums) { const s = new Set(nums); let ans = 0; const d = new Map(); for (const x of nums) { let y = x; while (s.has(y)) { s.delete(y++); } d.set(x, (d.get(y) || 0) + (y - x)); ans = Math.max(ans, d.get(x)); } return ans; };

对应仓库文件：Solution.js

复杂度与正确性分析

• 时间复杂度 O(n)：表面上看外层遍历n次、内层while循环可能走很多步，但关键在于「找到即删除」——集合s中的每个元素至多被删除一次，因此所有轮次的while循环迭代次数总和不超过n，加上n次哈希查找，均摊总工作量是线性的。
• 空间复杂度 O(n)：哈希集合与长度表各存O(n)个键。
• 拼接为什么与遍历顺序无关：以示例 1[100,4,200,1,3,2]走一遍：处理4时扫到5断掉，记d[4] = 1；随后处理1时向右扫1→2→3后在4处断掉（4已被删除），此时d[1] = d[4] + (4-1) = 1 + 3 = 4，恰好把先处理过的段[4]拼接进来得到完整段[1,2,3,4]。无论先遇到段尾还是段头，d都能正确继承前序长度，最终ans = 4。
• 重复元素的处理：方法一直接遍历原数组nums，重复值会进入多轮处理，但被删空后再次处理该值时while循环立即退出，d[x]重写为与旧值一致的结果，不影响答案（示例 3[1,0,1,2]中1出现两次即此情形）。

方法二：哈希集合（优化：只从起点扩展）

思路

思考（继承自原文档）：方法一额外用哈希表记下每段长度以便拼接。若只从「x-1不在集合中」的位置开始向右数，则x一定是某段起点，不必再保存d。实现更短，仍保证每个数被访问常数次。

核心观察：当x - 1不在集合s中时，x一定是某条连续段的起点（它的前驱缺失，没有任何更小的值能「代表」它）。因此只需对起点执行向右扩展：

1. 用哈希集合s存储所有元素；
2. 遍历集合，若x - 1在s中则直接跳过（x不是起点）；
3. 否则从y = x + 1开始不断y++，直到y不在s中；该段长度为y - x，更新ans。

与「删除式」方法一不同，方法二不修改集合，只读地统计长度，代码更短、更不易出错。

代码实现

Python3

class Solution: def longestConsecutive(self, nums: List[int]) -> int: s = set(nums) ans = 0 for x in s: if x - 1 not in s: y = x + 1 while y in s: y += 1 ans = max(ans, y - x) return ans

对应仓库文件：Solution2.py

Java

class Solution { public int longestConsecutive(int[] nums) { Set<Integer> s = new HashSet<>(); for (int x : nums) { s.add(x); } int ans = 0; for (int x : s) { if (!s.contains(x - 1)) { int y = x + 1; while (s.contains(y)) { ++y; } ans = Math.max(ans, y - x); } } return ans; } }

对应仓库文件：Solution2.java

C++

class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> s(nums.begin(), nums.end()); int ans = 0; for (int x : s) { if (!s.contains(x - 1)) { int y = x + 1; while (s.contains(y)) { y++; } ans = max(ans, y - x); } } return ans; } };

对应仓库文件：Solution2.cpp

Go

func longestConsecutive(nums []int) (ans int) { s := map[int]bool{} for _, x := range nums { s[x] = true } for x, _ := range s { if !s[x-1] { y := x + 1 for s[y] { y++ } ans = max(ans, y-x) } } return }

对应仓库文件：Solution2.go

TypeScript

function longestConsecutive(nums: number[]): number { const s = new Set<number>(nums); let ans = 0; for (const x of s) { if (!s.has(x - 1)) { let y = x + 1; while (s.has(y)) { y++; } ans = Math.max(ans, y - x); } } return ans; }

对应仓库文件：Solution2.ts

Rust

use std::collections::HashSet; impl Solution { pub fn longest_consecutive(nums: Vec<i32>) -> i32 { let s: HashSet<i32> = nums.iter().cloned().collect(); let mut ans = 0; for &x in &s { if !s.contains(&(x - 1)) { let mut y = x + 1; while s.contains(&y) { y += 1; } ans = ans.max(y - x); } } ans } }

对应仓库文件：Solution2.rs

JavaScript

/** * @param {number[]} nums * @return {number} */ var longestConsecutive = function (nums) { const s = new Set(nums); let ans = 0; for (const x of nums) { if (!s.has(x - 1)) { let y = x + 1; while (s.has(y)) { y++; } ans = Math.max(ans, y - x); } } return ans; };

对应仓库文件：Solution2.js。注意此版本遍历的是nums而非s，重复值会触发多次相同的「起点判定 + 扩展」，不影响正确性（重复值对应的x-1 in s判定一致）。

复杂度与正确性分析

• 时间复杂度 O(n)：所有x - 1 not in s的判定共O(n)次；while循环的y++总次数等于「所有连续段内部元素数之和」，每条连续段的内部元素只属于一个起点，故总和不超过n。示例 2[0,3,7,2,5,8,4,6,0,1]去重后为{0,1,2,3,4,5,6,7,8}，唯一起点是0（-1不在集合中），从0一路数到9断掉，ans = 9 - 0 = 9。
• 空间复杂度 O(n)：只需一个哈希集合，比方法一省掉长度表d。

两种方法的对比与工程取舍

从仓库中两套源码的结构可以推断：两种方法在实际工程中都成立，日常题解/面试推荐方法二——逻辑分支少、无「删除 + 拼接」的心智负担，且空间更省；方法一的价值在于展示了「用删除保证均摊线性」与「段长继承」这两个技巧，在需要动态维护连续段的更复杂问题中（例如边插入边查询最长连续段）这类拼接思想仍可复用。

边界与数值安全：

• 空数组（nums.length = 0）时集合为空，两种实现均直接返回0，与题目允许0长度输入一致；
• 负数无特殊处理，哈希集合天然支持；
• 关于y自增的溢出：题目约束nums[i] <= 10^9，y最多推进到10^9 + 10^5量级，远小于 32 位有符号整数上限（约2.1×10^9），因此 C++ 的int与 Rust 的i32在当前题目约束下均安全；若未来约束放宽到接近INT_MAX，y + 1存在溢出风险，需要改用 64 位整型——这是阅读 Solution2.cpp 等 C++/Rust 实现时值得注意的前提条件。

相关文件索引

该题属于 doocs/leetcode 仓库solution/0100-0199目录下的常规题解组织方式：README.md承载题面与思路，Solution*.py/java/cpp/...存放可运行源码，Solution2*对应第二解法，读者可直接对照本文代码在本地运行验证。

• 示例工程