算法题解模板

一份完整题解不能只贴通过的代码。读者需要先知道题意和数据范围，再理解为什么算法正确，最后才能判断代码是否适合自己的题目版本。

用途

记录一道算法题或竞赛题的题意、输入输出和数据范围。
说明从朴素思路到可行算法的推导过程。
给出正确性证明、时间复杂度和空间复杂度。
提供可运行代码、边界测试和常见错误提醒。

放在哪里

题解仍然是文章，放在 docs/posts/算法竞赛/ 下。可以在一级分类下，也可以按专题放进二级目录。

场景	目标文件	`categories`	`permalink`	公开地址
一级分类下	`docs/posts/算法竞赛/10.two-sum.md`	`[算法竞赛]`	`/posts/算法竞赛/two-sum`	`https://www.baecon.cn/posts/算法竞赛/two-sum`
专题子目录下	`docs/posts/算法竞赛/图论/20.shortest-path.md`	`[算法竞赛]`	`/posts/算法竞赛/图论/shortest-path`	`https://www.baecon.cn/posts/算法竞赛/图论/shortest-path`

公式：

text

文件：docs/posts/<一级分类>/[<子目录>/]<slug>.md
permalink：/posts/<一级分类>/[<子目录>/]<slug>
公开地址：https://www.baecon.cn/posts/<一级分类>/[<子目录>/]<slug>

「图论」是二级目录，不是第二个分类。categories 仍只写 [算法竞赛]。如果专题目录需要入口，另外创建对应目录页。

什么时候使用

你完成了一道算法题，并且代码已经通过题目给出的测试或评测。
需要记录题目来源、输入输出、数据范围和边界条件。
需要解释算法为什么正确，而不只是写「这样写就能过」。
需要沉淀可复用的技巧、复杂度和易错点。

什么时候不要使用

内容不是具体题目，而是算法知识点总结或训练计划：使用通用文章模板。
只是记录比赛过程、项目复盘或生活感受：使用对应模板。
题目来源、题面和限制不清楚，或不允许公开转载题面。此时应只写自己的思路并链接到原题，不要大段复制受版权保护的题面。
代码尚未验证，或无法说明正确性。不要用「显然」「容易证明」跳过关键推导。

完整可复制文件

markdown

---
title: 两数之和题解
description: 使用哈希表在线性时间内解决两数之和问题，包含题目来源、数据范围、思路推导、正确性证明、复杂度分析、C++ 代码和易错边界。
permalink: /posts/算法竞赛/two-sum
categories:
  - 算法竞赛
tags:
  - 哈希表
  - 数组
  - 两数之和
article: true
sidebar: true
pagefind-indexed: true
comment: true
---

# 两数之和题解

用一两句话说明题目来源、核心算法和结论。若题面来自在线评测平台，请注明来源并确认转载范围；不确定时只概述题意并链接原题。

## 题目

给定一个整数数组 `nums` 和一个整数目标值 `target`，请在数组中找出和为目标值的两个整数，并返回它们的下标。

题目保证每个输入最多只有一个有效答案，且同一个元素不能使用两次。答案下标顺序不限。

输入示例：

```text
nums = [2, 7, 11, 15], target = 9
```

输出示例：

```text
[0, 1]
```

因为 `nums[0] + nums[1] = 2 + 7 = 9`。

> 题目来源：替换为原题名称和链接，并确认题面转载许可。若不能公开题面，请删除大段题面，只保留自己的题意概括。

## 数据范围

| 参数 | 范围 | 对算法的影响 |
|---|---|---|
| `n` | `2 <= n <= 100000` | 双重循环的 `O(n²)` 在最大数据下不可接受 |
| `nums[i]` | `-10^9 <= nums[i] <= 10^9` | 两数相加可能超出 32 位整数，计算补数时使用 64 位 |
| `target` | `-10^9 <= target <= 10^9` | 需要判断无解情况，不能假设一定有解 |
| 答案数量 | 最多一个 | 找到即可返回，不需要枚举所有组合 |

## 思路

最直接的方法枚举所有 `i < j`，检查 `nums[i] + nums[j] == target`，时间复杂度为 `O(n²)`。当 `n` 达到十万时无法接受。

观察等式：

```text
nums[i] + nums[j] = target
```

固定当前下标 `j` 时，只需要知道之前是否出现过：

```text
need = target - nums[j]
```

因此可以在遍历时用哈希表记录「已经出现过的数值 → 下标」。对每个 `nums[j]`，先查询 `need`；如果存在，直接返回两个下标；否则把当前值和下标存入哈希表。

示例过程：

```text
target = 9
nums = [2, 7, 11, 15]

处理 2：need = 7，哈希表中没有 7，存入 2 -> 0
处理 7：need = 2，找到 2 -> 0，返回 [0, 1]
```

先查询再插入，可以避免同一个元素被使用两次。

## 正确性证明

**命题**：若输入存在一组合法答案 `i < j` 且 `nums[i] + nums[j] = target`，算法一定返回一组合法下标；若算法返回下标，它们一定对应两个不同位置且和为目标值。

**充分性证明**：

假设存在合法答案 `i < j`。算法按顺序处理元素。处理到下标 `j` 时，下标 `i` 已经被处理并存入哈希表。此时：

```text
need = target - nums[j] = nums[i]
```

因此哈希表查询一定能找到 `nums[i]`，并在当前步骤返回 `[i, j]`。

**正确性证明**：

如果算法在某一步返回 `[seen[need], j]`，那么 `seen[need]` 是一个之前处理过的下标 `i`，因此 `i < j`，两个下标不同；同时：

```text
nums[i] + nums[j] = need + nums[j] = (target - nums[j]) + nums[j] = target
```

所以返回的是一组合法答案。

**无解时**：如果遍历结束仍未找到，说明对每个 `j`，之前都没有与之互补的值。结合每个元素只与之前元素配对，所有可能的 `i < j` 已被覆盖，因此不存在合法答案，返回空结果正确。

## 复杂度

| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | 平均 `O(n)` | 每个元素至多一次哈希表查询和一次插入，平均单次为 `O(1)` |
| 空间复杂度 | `O(n)` | 最坏情况下需要存储所有已处理元素及其下标 |
| 最坏情况备注 | 哈希表理论上可能退化 | 竞赛中通常按平均复杂度分析，必要时使用更稳定的哈希方式 |

## 代码

以下代码使用 `long long` 计算补数，避免极端值相减溢出。

```cpp
#include <bits/stdc++.h>
using namespace std;

vector<int> twoSum(const vector<long long>& nums, long long target) {
    unordered_map<long long, int> seen;
    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        long long need = target - nums[i];
        auto it = seen.find(need);
        if (it != seen.end()) {
            return {it->second, i};
        }
        seen[nums[i]] = i;
    }
    return {};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> nums(n);
    for (long long& x : nums) cin >> x;

    long long target;
    cin >> target;

    vector<int> ans = twoSum(nums, target);
    if (ans.empty()) {
        cout << "No solution\n";
    } else {
        cout << ans[0] << ' ' << ans[1] << '\n';
    }
    return 0;
}
```

输入：

```text
4
2 7 11 15
9
```

预期输出：

```text
0 1
```

## 易错点

- 把「返回值」误写成「返回下标」，或把题目要求的下标起点弄错。
- 先插入当前元素再查询，导致同一个下标被使用两次。
- 数组中有重复值时，哈希表会覆盖旧下标；本题一旦找到答案就返回，因此不影响正确性，但要确认题目是否要求所有答案。
- 使用 32 位整数计算 `target - nums[i]` 可能溢出。
- 忘记处理无解情况，直接返回未初始化的下标。
- 只证明「算法能找到答案」，没有证明「算法返回的答案一定合法」。
- 复杂度写着 `O(n)`，却在校验或输出阶段写了嵌套循环，实际复杂度仍然是 `O(n²)`。

## 总结

本题的核心是空间换时间：用哈希表保存已经出现过的数值与下标，把两数之和转化为一次补数查询。可复用的模板是「遍历当前元素 → 查询历史信息 → 更新历史信息」。需要特别说明下标不可重复、溢出和无解三个边界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185

复制后必须修改或确认

值	位置	应该怎么改	为什么必须确认
`title` 和正文 H1	frontmatter 与 `# 两数之和题解`	改成完全一致的题解标题	页面只能有一个 H1，标题会进入首页、侧边栏和搜索。
`description`	frontmatter	换成 50–150 个中文字符的题解摘要	说明题名、核心算法和复杂度，不要只写「题解」。
`date`	frontmatter	通常不要手填；文件首次 Git commit 后启动/构建会自动写入	自动写入后不要为了「更新」而改它；更新信息用 `updated`。
`permalink`	frontmatter	改成全站唯一且匹配目录的 `/posts/算法竞赛/.../slug`	避免不同题目使用同一个永久链接。
`categories`	frontmatter	只写 `[算法竞赛]`	专题目录不是第二个分类。
`tags`	frontmatter	换成 2–5 个算法、数据结构或题名标签	标签要具体，便于按方法检索。
`coverImg`	frontmatter	通常删除以使用正文图片/随机背景；只在需要固定卡片或分享图时写真实路径	显式写后会固定，不再随机；路径必须存在。
`article`	frontmatter	保持 `true`	确保题解进入文章区域。
`sidebar`	frontmatter	保持 `true`	让读者能访问文章导航。
`pagefind-indexed`	frontmatter	保持 `true`	题解通常需要被搜索；它不是访问控制。
`comment`	frontmatter	保持 `true`	允许读者讨论错误和补充；关闭时改 `false`。
题面与来源	body	换成获准公开的题意概括和原题链接	不要大段复制受版权保护或未授权的题面。
数据范围、证明、复杂度、代码	body	换成实际题目的范围、证明、复杂度和已通过代码	示例题解不能直接当作其他题目的答案。

可选字段

字段	什么时候用	推荐值	注意
`titleTag`	想标示这是一篇题解	`题解`	只是标题旁短标签，不替代 tags。
`top`	题解需要进入首页精选	`1`	真值标记，不是排名。
`sticky`	需要置顶排序	`1` 或较小数字	必须是数字，越小越靠前。
`sidebarSort`	需要覆盖侧边栏顺序	`10`、`20`	优先使用文件名数字前缀。
`inHomePost`	不想让题解进入首页主列表	省略或 `false`	会影响首页及分类/标签的 HomePost 列表，不是隐私设置。
`updated`	需要覆盖 SEO 修改时间	`YYYY-MM-DD HH:mm:ss`	通常省略，不能代替 `date`。
`author`	多人共同解题并需要署名	不写；如确需覆盖，用对象 `{ name, link }`	本站默认站点作者，普通题解不要覆盖。

文章 frontmatter 字段总表

字段	类型	省略时默认	推荐值	级别	完整说明
`title`	`string`	无可用默认；不要依赖自动推导	与正文唯一 H1 完全一致	必填	页面标题，也是首页卡片、侧边栏、搜索结果和浏览器标题的来源。复制模板后必须改成真实标题，并保证正文只有一个 H1。
`description`	`string`	SEO 会回退到站点描述；首页摘要质量不可控	50–150 个中文字符，说明问题、内容与读者收益	推荐	供 SEO 描述、首页卡片摘要和分享信息使用。应写成完整的一句话或两句话，不要堆关键词，也不要直接复制标题。
`desc`	`string`	未设置	省略	可选（旧字段）	旧目录页的兼容显示字段，主要给 catalogue 页面使用；它不是 SEO 主字段，也不参与首页摘要。新文章不要写；目录页如保留 `desc`，需与 `description` 同值。
`date`	`string`	文件首次 Git commit 的作者时间；已有值保留	通常省略，不手填；需要人工指定发布时间时才覆盖	自动维护；通常不手填	文章的创建/发布时间，用于展示、首页排序、归档和 SEO 的 `datePublished`。新文章不需要写；首次 commit 后启动/构建会写入并保持稳定。
`updated`	`string`	未显式设置；SEO 修改时间由构建或最后更新时间兜底	正常省略；确实需要覆盖时再用同一日期格式	可选	只用于覆盖 SEO 的 `dateModified`，不是文章发布时间，也不能代替 `date`。除非有明确的更新日期要展示给搜索引擎，否则不要填。
`permalink`	`string`	自动插件通常跳过已有 frontmatter，不能依赖自动生成	全站唯一：`/posts/<一级分类>/[<子目录>/]<slug>`	必填	决定文章的公开 URL。本项目要求显式填写，不能包含 `.md`，不能以 `docs/` 开头，也不能与其他页面重复。
`categories`	`string[]`	自动插件通常跳过；缺省时没有可靠分类	显式写一级分类，如 `[技术笔记]`	推荐	分类归档和分类卡片使用。只写一级分类；二级目录属于路径，不是第二个分类。一篇文章通常只写一个一级分类。
`tags`	`string[]`	`[]`	2–5 个具体标签，如 `[VitePress, 部署]`	推荐	标签用于聚合主题和搜索。标签应短而具体，避免把整句话、分类名或大量近义词都写成标签。
`coverImg`	`string` 或 `string[]`	首页卡片：正文图片随机 → `/home/bg*.webp` 随机；SEO 分享图回退站点默认	需要固定封面/分享图时才写真实路径；否则省略	可选（按需）	首页卡片优先使用；文章 Banner、OG 和分享图也会读取。显式写后不再随机；路径必须真实存在；不写时分享图不会自动取正文图。
`article`	`boolean`	在 `/posts/` 下省略时按 `true` 处理	`true`	推荐	明确声明这是文章，让首页、归档、分类和标签等文章能力正常工作。教程、复盘、随笔、题解和建站记录都应显式写 `true`。
`sidebar`	`boolean`	VitePress 默认为 `true`	`true`	推荐	控制文章页是否显示左侧文章导航。本站文章应保持 `true`；只有特殊全宽页面才考虑关闭。
`sidebarSort`	`number`	使用文件名数字前缀；没有前缀时按 `9999`	省略；确需覆盖时用 `10`、`20` 这类数字	可选	覆盖该文章在侧边栏中的排序，数字越小越靠前。优先用文件名前缀排序；同时使用两种方式会增加理解和维护成本。
`pagefind-indexed`	`boolean`	`true`	`true`	推荐	控制 Pagefind 是否索引此页。文章应保持 `true`；设为 `false` 只是不进入站内搜索，并不会把页面变成私有页面。
`comment`	`boolean`	未写 `false` 时按开启处理	`true`	推荐	控制文章评论区。普通文章保持 `true`；目录页、纯功能页或含敏感信息的页面应关闭或不要发布。
`top`	`boolean 或 number`	未设置，即不进入精选	省略；只有需要首页精选时写 `1`	可选	首页「精选文章」的真值筛选标记，不是排名：写 `1` 表示入选，数字大小本身不会排序。是否显示还受首页精选数量上限影响。
`sticky`	`number`	未设置，即不置顶	省略；确需置顶时用较小数字，如 `1`	可选	置顶排序字段，数字越小越靠前。它和 `top` 分工不同：`top` 负责进入精选卡片，`sticky` 负责置顶排序。不要用 `true` 代替数字。
`inHomePost`	`boolean`	`true`	省略或显式 `true`；只有特殊文章才写 `false`	可选	设为 `false` 时会从首页、分类页和标签页等 HomePost 列表隐藏；文章的 URL、侧边栏、归档、精选和搜索等不会自动变成私有。不要把它当作隐私开关。
`inCatalogue`	`boolean`	`true`	通常省略；不想让文章出现在目录页时写 `false`	高级	目录插件扫描开关；不影响侧栏、Pagefind、首页、归档或 RSS。
`titleTag`	`string`	无标签	省略；需要短标识时用 `原创`、`教程`、`复盘`、`题解`、`记录`	可选	标题旁的小标签，只用于视觉提示，不替代分类或标签。保持 2–4 个汉字最清晰，不要塞入长句。
`author`	`object`	使用站点级作者 `Baecon`	省略，不在单篇文章覆盖	可选（不建议）	若覆盖需用 `{ name: string, link?: string }` 对象；普通文章不要填写。

高级 VitePress 字段

以下字段控制页面布局，不是题解内容。算法题解通常全部省略，使用默认文章布局即可。

字段	类型	省略时默认	推荐值	级别	完整说明
`layout`	`string 或 false`	使用 VitePress 标准文章布局	省略	高级	切换页面布局。文章模板不需要设置；目录页才固定使用 `layout: page`。初学者不要为了外观而改它。
`outline`	`false`、数字、`[number, number]` 或 `"deep"`	由 VitePress 与主题的默认大纲配置决定	省略	高级	控制右侧标题大纲。普通文章沿用站点统一配置即可，除非全站规范明确要求，否则不要逐篇覆盖。
`aside`	`boolean` 或 `"left"`	默认跟随 VitePress 文章布局	省略	高级	控制右侧辅助栏。与全站布局相关，不应由每篇文章随意切换。
`lastUpdated`	`boolean`	跟随站点 `lastUpdated: true`	省略	高级	控制页面是否显示最后更新时间。本站已统一开启，不需要在每篇文章重复设置。
`editLink`	`boolean`	跟随站点主题配置	省略	高级	控制是否显示编辑链接。它属于站点能力，不是文章内容字段。
`pageClass`	`string`	空	省略	高级	给页面根元素追加 CSS 类，只在有配套样式时使用。随意填写不会产生视觉效果。
`layoutClass`	`string`	空	省略	高级	当前项目会把它作为布局组件 class 读取，但只有配套 CSS 才有意义；普通写作不需要填写。
`head`	`array`	`[]`	省略	高级	为单个页面追加 `<head>` 标签。站点已统一生成 SEO 和分享标签，重复配置容易冲突。
`titleTemplate`	`string 或 false`	使用站点标题模板	省略	高级	覆盖浏览器标题拼接方式。除非页面有特殊 SEO 要求，否则不要覆盖全站一致性。
`autoTitle`	`boolean`	doc 布局默认允许自动注入 H1	省略；正文已手写 H1	高级	设为 `false` 可禁止自动 H1 注入。
`articleUpdate`	`boolean 或 object`	跟随站点配置，默认启用	省略	高级	设为 `false` 隐藏文章页最近更新模块。
`articleBanner`	`boolean 或 object`	跟随站点配置；本站开启	省略	高级	设为 `false` 关闭单文章 Banner；通常仅无侧栏 doc 文章生效。
`coverBgColor`	`string`	跟随站点 defaultCoverBgColor，本站为空	省略	高级	单文章 Banner 背景色覆盖；无 Banner 时不可见。
`prev`	`boolean`	`true`（有上一页时）	省略	高级	设为 `false` 隐藏上一页链接。
`next`	`boolean`	`true`（有下一页时）	省略	高级	设为 `false` 隐藏下一页链接。

catalogue、path、pageTitle 是目录页专用字段，文章模板不要填写。若需要创建分类或子目录入口，请使用目录页模板。

章节	写什么	示例
`## 题目`	用自己的话概述题意、输入输出和答案要求	注明题目来源与转载限制。
`## 数据范围`	参数范围、值和答案规模、对算法选择的影响	用表格写范围与推论。
`## 思路`	从朴素做法推导到可行算法，包含关键观察	写清哈希表保存什么。
`## 正确性证明`	证明算法返回的答案合法，且不会漏掉合法答案	分充分性和必要性或分情况讨论。
`## 复杂度`	时间复杂度、空间复杂度和分析前提	哈希表要注明平均或最坏情况。
`## 代码`	可运行的完整代码和必要输入输出说明	标注语言、标准或评测环境。
`## 易错点`	边界、溢出、下标、重复值、初始化等问题	写「现象 / 原因 / 修正」。
`## 总结`	提炼可复用的算法思想和模板	不重复整段证明。