C++求两数之和并返回下标详解

前言「两数之和」要求在一个整数数组里找出两个数使它们的和等于目标值并返回这两个数的下标。它是哈希表最经典的应用场景也是很多人接触「用空间换时间」的第一个例子。题目本身不难但要把边界写对、把重复元素处理对、把返回值约定说清楚仍然有不少细节。最常见的误解是「先建表再查找」。如果先把整个数组塞进哈希表再遍历查找补数那么当两个下标指向同一个元素时例如目标值是某个元素的两倍会错误地把同一个位置用两次。正确做法是「边查边建」对当前元素先问表里有没有它的补数没有再把当前元素放进去。这样保证查到的补数一定来自更早的位置两个下标天然不同。第二个误解是认为哈希表解法的复杂度是严格 O(n)。准确说法是平均 O(n)最坏情况取决于哈希函数与冲突处理理论上可以退化。本文会说明这一点并给出暴力法、哈希法、排序双指针法三种实现及各自的适用条件。一、问题定义与返回值约定输入是一个整数序列nums和一个目标值target要求返回一对下标(i, j)满足i ! j且nums[i] nums[j] target。题目通常保证有且仅有一组答案但工程代码不应依赖这个假设需要定义「无解」时返回什么。返回类型的选择会影响接口的清晰度。如果确定有解可以返回std::pairstd::size_t, std::size_t如果可能无解用std::optionalstd::pair...更直接如果可能有多组解返回std::vectorstd::vectorstd::size_t。用「返回空 vector」表示无解是一种常见约定但它与「答案就是空」无法区分严格来说不如std::optional明确。下标类型建议用std::size_t而不是int。std::vector的size()返回std::size_t用int接收会引入有符号与无符号的混用在超大数组上还可能溢出。代价是打印时要记得用%zu或先转换。二、暴力法与它的价值暴力法枚举所有i j检查和是否等于目标。时间复杂度 O(n²)空间 O(1)。它在面试里通常不是最终答案但有两个价值一是作为对照实现用来验证优化版本的结果二是当 n 很小比如小于 32时它的常数因子低实际可能比哈希表更快。// 适用于 C17#include cstddef#include utility#include vector#include optionalstd::optionalstd::pairstd::size_t, std::size_ttwo_sum_brute(const std::vectorint nums, int target) {for (std::size_t i 0; i nums.size(); i) {for (std::size_t j i 1; j nums.size(); j) {// 用 long long 计算和避免 int 相加溢出if (static_castlong long(nums[i]) nums[j] target) {return std::make_pair(i, j);}}}return std::nullopt;}这里把加法提升到long long不是为了性能而是为了正确性两个int相加可能溢出而有符号整数溢出是未定义行为undefined behavior, UB不能写成「溢出后回绕成负数再比较」。在int为 32 位、target也接近边界时这个细节会真的影响结果。三、哈希表边查边建哈希法的核心是把「找补数」从线性扫描变成常数时间查询。遍历数组对每个元素x计算need target - x如果表里已经有need说明之前某个位置与当前位置构成答案否则把x和它的下标存入表中。顺序很重要先查后插。如果先插入再查当前元素会查到自己当2 * x target时会返回同一个下标两次。// 适用于 C17#include cstddef#include optional#include unordered_map#include utility#include vectorstd::optionalstd::pairstd::size_t, std::size_ttwo_sum_hash(const std::vectorint nums, int target) {std::unordered_maplong long, std::size_t seen;seen.reserve(nums.size()); // 预留桶数减少 rehashfor (std::size_t i 0; i nums.size(); i) {const long long need static_castlong long(target) - nums[i];auto it seen.find(need);if (it ! seen.end()) {return std::make_pair(it-second, i);}seen.emplace(static_castlong long(nums[i]), i);}return std::nullopt;}键类型用long long而不是int是为了让need的计算不溢出。若用int作键target - nums[i]在极端值下会溢出UB而且溢出后的值可能恰好命中表里的某个键产生错误答案。用long long存键后nums[i]转成long long再参与减法结果一定在long long范围内。重复元素在这套逻辑下是安全的。以nums {3, 3}、target 6为例i 0 时need 3表为空插入3 → 0i 1 时need 3命中返回(0, 1)。两个下标不同答案正确。如果数组是{3, 1, 3}、target 6i 2 时命中 0返回(0, 2)同样正确。reserve(nums.size())不是必须的但它能减少插入过程中的重新哈希。unordered_map的桶数会随元素增加而增长每次增长都要重新分布所有元素提前预留可以把这个开销摊掉。代价是内存占用略高。至于reserve之后是否还会 rehash取决于实现的最大负载因子标准只规定平均情况下的复杂度不规定具体的桶数与增长策略。复杂度平均 O(n) 时间、O(n) 空间。最坏情况下如果所有键都落到同一个桶哈希函数被恶意构造或质量很差单次查找退化为 O(n)整体 O(n²)。这也是「哈希表严格 O(n)」说法不准确的原因。实际使用中标准库的哈希函数对整数通常是恒等映射再混合配合质数桶数退化很少发生但不能当成数学保证。四、排序加双指针另一种思路如果数组已经有序可以用双指针左指针指向最小元素右指针指向最大元素计算两数之和和小于目标就左指针右移和大于目标就右指针左移。时间 O(n)空间 O(1)。但题目要求返回原始下标排序会打乱下标所以必须把「值 原下标」一起排序或者先复制一份带下标的数组。// 适用于 C17#include algorithm#include cstddef#include optional#include utility#include vectorstd::optionalstd::pairstd::size_t, std::size_ttwo_sum_sorted(std::vectorint nums, int target) {std::vectorstd::pairint, std::size_t items;items.reserve(nums.size());for (std::size_t i 0; i nums.size(); i) {items.emplace_back(nums[i], i);}std::sort(items.begin(), items.end());std::size_t lo 0;std::size_t hi items.size();while (lo 1 hi) {const long long sum static_castlong long(items[lo].first) items[hi - 1].first;if (sum target) {return std::make_pair(items[lo].second, items[hi - 1].second);} else if (sum target) {lo;} else {--hi;}}return std::nullopt;}这种写法适合「数组已排序」或「需要多次查询同一数组」的场景排序一次 O(n log n)之后每次查询 O(n)。如果只查一次排序的 O(n log n) 反而比哈希的 O(n) 慢除非内存受限、不能用哈希表。注意hi初始化为items.size()而不是size() - 1循环条件是lo 1 hi这样hi - 1始终是有效下标空数组时循环一次也不进。这是半开区间写法在双指针上的应用。五、三种方法对比方法平均时间最坏时间额外空间是否保留原下标适用场景暴力枚举O(n²)O(n²)O(1)是小数组、对照验证哈希表O(n)O(n²)O(n)是通用单次查询排序双指针O(n log n)O(n log n)O(n)需要额外记录已排序或多次查询选型的判断顺序是先看数组是否已经有序有序就用双指针否则看内存是否宽裕宽裕就用哈希两者都不满足才退回暴力。不要为了「看起来高级」在小数组上强行引入哈希表构造与销毁哈希表的开销在 n 很小时不可忽略。常见坑点坑点一先插入再查找导致同一元素被用两次。❌seen[nums[i]] i;写在find之前nums {3}、target 6时返回(0, 0)。✅ 先find(need)未命中再插入当前元素。坑点二用int计算target - nums[i]。❌int need target - nums[i];极端值下溢出属于 UB。✅ 提升到long long计算键类型也用long long。坑点三用int表示下标。❌for (int i 0; i nums.size(); i)有符号与无符号比较产生警告。✅ 用std::size_t或 C20 起用std::ranges::ssize获取有符号长度。坑点四返回空 vector 表示无解却当成有解处理。❌ 调用方不检查result.empty()就直接取result[0]。✅ 用std::optional表达「可能无解」或调用前显式判断。坑点五以为哈希表最坏也是 O(n)。❌ 在复杂度分析里写「哈希法严格 O(n)」。✅ 写「平均 O(n)最坏 O(n²)取决于哈希质量与冲突」。坑点六排序双指针直接对原数组排序丢失原始下标。❌std::sort(nums.begin(), nums.end());之后返回排序后的位置。✅ 把值和原下标绑成 pair 一起排序返回second。坑点七双指针的右边界初始化错位。❌std::size_t hi nums.size() - 1;在空数组时下溢为SIZE_MAX。✅ 用半开区间hi nums.size()循环条件lo 1 hi。坑点八认为题目保证有解就不写无解分支。❌ 函数末尾没有return编译器报「控制流到达非 void 函数末尾」。✅ 显式返回std::nullopt或空容器。总结要点结论核心思路用哈希表把「找补数」降为常数时间关键顺序先查后插避免同元素复用溢出防护补数与和都用long long计算重复元素边查边建天然正确处理下标类型优先std::size_t无解表达std::optional优于空容器两数之和的代码只有十几行真正需要想清楚的是三件事查询与插入的先后、加法是否会溢出、无解时返回什么。把这三点定下来哈希版本就是正确且高效的剩下的排序双指针只是另一种权衡在数组本来就有序时才有优势。