企业官网建设流程全解析

• 科学计算

导读

本篇技术指南以 leetcode/biweekly/121/a/README.md 题解文档为核心，深入讲解力扣双周赛第 121 场 A 题《最小缺失整数》（Smallest Missing Integer Greater Than Sequential Prefix Sum）的完整解法：先遍历数组求最长连续递增前缀的元素和，再用哈希集合从该前缀和出发逐步自增，找到第一个不在数组中的整数。读完本文，你将掌握这道题的两阶段线性算法、四语言（Python/Java/C++/Go）代码模板、边界用例（如1324567），以及本仓库如何用a.go、a.txt与a_test.go组成"题解 + 样例数据 + 自动化测试"的完整闭环。

一、题目核心：顺序前缀和是什么

题目要求：给定整数数组nums，先求出"最长的顺序前缀"的元素之和s——所谓顺序前缀，是指从nums[0]开始、每个元素都比前一个元素恰好大1的连续前缀；随后不断将s加1，直到s不再出现在nums中，此时返回s。

为什么是"前缀"而不是任意子段

原文档明确了两点关键约束：

• 前缀必须从nums[0]开始，也就是只能从数组头部向后延伸；
• 前缀内相邻元素严格满足x + 1 == y（连续整数），一旦断链（例如nums[i] != nums[i-1]+1）就立刻停止累加。

例如nums = [1, 2, 3, 2, 5]：

1. 最长顺序前缀是[1, 2, 3]，其和为s = 6；
2. 6不在数组中，直接返回6。

再如nums = [3, 4, 5, 1, 12, 14, 13]：

1. 最长顺序前缀是[3, 4, 5]，s = 12；
2. 但12在数组中，于是s依次变为13（仍在数组中）、14（仍在数组中）、15（不在数组中），最终返回15。

这两个样例正是仓库中 a.txt 里存储的测试数据，一并在下节验证。

二、算法思路：两阶段线性扫描

阶段一：求最长顺序前缀的和

从nums[0]出发，初始化s = nums[0]；从第二个元素开始向后检查，只要nums[i] == nums[i-1] + 1就继续把nums[i]累加进s，否则立即跳出循环。由于前缀要求"从nums[0]起连续"，这里用&&短路同时判断越界与连续性，一旦断链就终止，因此前缀不可能从中间某个位置重新开始。

阶段二：从s出发找最小缺失整数

将整个nums装入哈希集合，然后反复执行：

while s 在集合中: s += 1

每次把s加1都是因为s本身"被占用了"；一旦s不在集合中，就得到了答案。这个循环至多执行n次（n为数组长度），因为当s增长到超过数组中最大值后必然不在集合中——原文档给出的极端例子是nums = [1, 3, 2, 4, 5, 6, 7]（即1324567）：此时最长顺序前缀是[1]，s = 1，1在数组中，之后依次跳过2,3,4,5,6,7七个元素，s最终变成8才跳出循环，恰好循环了n = 7次。

复杂度分析（原文档结论）

• 时间复杂度：O(n)，其中n是nums的长度。阶段一是单次线性扫描，阶段二至多自增n次，哈希集合的插入与查询均摊O(1)；
• 空间复杂度：O(n)，用于存储哈希集合。

三、四语言代码模板（继承自原题解文档）

原文档给出了 Python3、Java、C++、Go 四份等价的实现，这里完整保留并补充注释：

class Solution: def missingInteger(self, nums: List[int]) -> int: s = nums[0] for x, y in pairwise(nums): if x + 1 != y: break s += y st = set(nums) while s in st: # 至多循环 n 次，例如 1324567 s += 1 return s

class Solution { public int missingInteger(int[] nums) { int sum = nums[0]; for (int i = 1; i < nums.length && nums[i] == nums[i - 1] + 1; i++) { sum += nums[i]; } Set<Integer> set = new HashSet<>(); for (int num : nums) { set.add(num); } while (set.contains(sum)) { // 至多循环 n 次，例如 1324567 sum++; } return sum; } }

class Solution { public: int missingInteger(vector<int>& nums) { int sum = nums[0]; for (int i = 1; i < nums.size() && nums[i] == nums[i - 1] + 1; i++) { sum += nums[i]; } unordered_set<int> s(nums.begin(), nums.end()); while (s.contains(sum)) { // 至多循环 n 次，例如 1324567 sum++; } return sum; } };

func missingInteger(nums []int) int { sum := nums[0] for i := 1; i < len(nums) && nums[i] == nums[i-1]+1; i++ { sum += nums[i] } has := map[int]bool{} for _, x := range nums { has[x] = true } for has[sum] { // 至多循环 n 次，例如 1324567 sum++ } return sum }

四种实现殊途同归：阶段一都用x + 1 == y（或nums[i] == nums[i-1] + 1）作为连续性判据；阶段二都用哈希结构（set/unordered_set/map[int]bool）做 O(1) 判重。注意s从nums[0]开始取值，即使第一个元素之后立即断链，也至少要返回一个不小于nums[0]的缺失整数。

四、仓库实现佐证：从a.go到自动化测试闭环

4.1 源码实现 a.go

仓库中的 Go 解答与题解文档的sol-Go完全一致（去掉了文档里has[sum]判断的注释）：

package main // https://space.bilibili.com/206214 func missingInteger(nums []int) int { sum := nums[0] for i := 1; i < len(nums) && nums[i] == nums[i-1]+1; i++ { sum += nums[i] } has := map[int]bool{} for _, x := range nums { has[x] = true } for has[sum] { // 至多循环 n 次 sum++ } return sum }

注意package main：仓库的力扣题解都以main包组织，便于直接用go test跑题解自测。

4.2 测试数据与测试用例

• 样例数据文件 a.txt 以"输入一行、期望输出一行、空行分隔"的格式组织，正好对应上面推演的两个用例：
  • 用例 1：输入[1,2,3,2,5]→ 输出6；
  • 用例 2：输入[3,4,5,1,12,14,13]→ 输出15。
• 测试文件 a_test.go 由模板生成器自动生成，其核心只有一行调用：

func Test_a(t *testing.T) { if err := testutil.RunLeetCodeFuncWithFile(t, missingInteger, "a.txt", 0); err != nil { t.Fatal(err) } }

RunLeetCodeFuncWithFile（定义于 leetcode/testutil/leetcode.go）会读取a.txt，按fNumIn + fNumOut（本题为 1 输入 + 1 输出 = 2 行）切分组数据，通过反射调用missingInteger，再把实际输出与期望输出逐例比对。targetCaseNum传0表示跑全部用例；传-1表示只跑最后一个用例（该参数在_test.go中默认以注释形式给出，可用于调试）。

• 该测试用例的题目链接记录在 a_test.go 末尾：biweekly-contest-121/problems/smallest-missing-integer-greater-than-sequential-prefix-sum/。

4.3 测试基础设施如何工作（仓库级深度）

RunLeetCodeFuncWithExamples（leetcode/testutil/leetcode.go）做了三件事，体现了本仓库"题解仓库"的工程化设计：

1. 解析输入：parseRawArg（leetcode/testutil/leetcode.go）按 Go 反射类型把[1,2,3,2,5]解析为[]int，把6解析为int；
2. 执行并做 TLE 检测：isTLE（leetcode/testutil/leetcode.go）在非调试环境下用带超时定时器的 goroutine 包裹被测函数，若超时直接报"【超时】"；
3. 断言输出：toRawString把反射到的结果序列化成[6]或15这类字符串，与期望值assert.Equal比对，出错时报"【答案错误 N】"并打印对应输入。

也就是说，即便你修改了a.go里的实现，只要go test ./leetcode/biweekly/121/a/（仓库根目录下执行），测试框架就会自动用a.txt里的官方样例做回归验证——这套"README 题解 +x.go实现 +x.txt样例 +x_test.go自动测试"的四件套模式，是仓库中每一道力扣题的标准形态（可参考同场次 b/README.md 等其他题目目录）。

五、扩展思考：为什么哈希集合是最优判重结构

本题第二阶段本质上是在问"从s开始，第一个不属于nums的整数是谁"。若改用数组 + 排序后二分查找，单次判断是O(log n)，总复杂度会退化到O(n log n)；而哈希集合把"是否包含"压到均摊O(1)，配合"至多n次自增"的结论，让整体保持O(n)。从代码结构看，本仓库中大量依赖集合语义的场景（如 copypasta/orderedset.go、copypasta/treap 等有序集合实现）处理的是"需要取前驱/后继"的更强操作；本题只需存在性查询，用map[int]bool或set即可，无需引入有序结构——这是"按需选择数据结构"的典型范例。

六、实战检验：跑通仓库测试

若你想在本地验证上面的完整链路（仓库为只读，以下均为查看与运行操作）：

1. 在仓库根目录（含 go.mod，模块名github.com/EndlessCheng/codeforces-go，Go 1.23）执行：

go test ./leetcode/biweekly/121/a/

2. 若只想调试单个用例，把 a_test.go 中的targetCaseNum改为1或2（分别对应a.txt中的两个样例），或利用RunLeetCodeFuncWithFile的负参数约定传-1跑最后一个用例；
3. 若本地没有这些文件对应的测试依赖，可先go mod download拉取 go.sum 中锁定的依赖再执行测试。

题解文档 README.md 末尾还附有"科学刷题"方法论与滑动窗口、二分、单调栈、网格图、位运算、图论、动态规划等分类题单，以及仓库作者维护的题解精选列表 leetcode/SOLUTIONS.md，可作为后续系统化练习的索引。

总结

本题的解题链非常清晰：阶段一用一次线性扫描求出从nums[0]开始的最长连续递增前缀的元素和s；阶段二用哈希集合从s逐次加1，返回第一个不在数组中的值。时间复杂度O(n)、空间复杂度O(n)，1324567这类极端样例恰好说明了"至多循环n次"的边界。配合仓库中 a.go、a.txt 与 a_test.go 组成的测试闭环，你可以立即动手复现、修改并验证任何等价实现。

• 科学计算