两数之和
Two Sum
在数组里找出两个数，使它们的和等于 target，返回这两个数的下标（每个数只能用一次，答案唯一）。
在力扣中练习题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6 输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6 输出：[0,1]
提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- 只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
解题思路
哈希表 · 一次遍历
不找「两个数」，改成找「一个数的搭档」
直接两层循环能找答案，但每个数都会反复查找同一批搭档。把已经看过的值与下标存在哈希表里，就能把“之前有没有 target-x”变成一次查询。
自拟主例：nums = [6,-2,5,6,10,1]，target = 12，唯一答案是下标 [0,3]。两个 6 数值相同，身份却不同；第一个 6 不能与自己配对。
先建立空哈希表。两个 6 是不同下标，不能拿同一个位置用两次。
因此顺序必须是先查搭档，再登记自己。扫描第二个 6 时，表里已经保存 6 → 0，直接返回 [0,3]。表中保存的是下标而不是出现次数，才能还原题目要求的两个位置。查找成功后立即返回，尚未扫描的元素不影响答案。
易错点
- 先存后查：target = 8、nums = [4, ...] 时会把同一个元素用两次。
- 返回 {i, j} 顺序反了 —— 本题虽不校验顺序，但按题目习惯返回小下标在前更稳妥。
- 用 map 而不是 unordered_map，复杂度退化成 O(n log n)。
暴力枚举
O(n²) 对照版，用来理解哈希表到底省掉了什么
结果正确，但最坏 O(n²)，大输入可能超时；仅用于与哈希表的一次扫描对照。
最直白的想法：枚举所有数对 (i, j)，判断 nums[i] + nums[j] == target。
内层循环从 i + 1 开始，天然保证每个元素只被用一次，也不会有重复数对。
它的问题不是「错」，而是「重复劳动」：对每个 i 都要把后面所有元素扫一遍。哈希表把这些扫描结果缓存了下来——这正是 O(n) 和 O(n²) 的差距来源。
数据规模 n ≤ 10⁴ 时暴力也能过，但面试里写出 O(n) 才是加分项。
- 1外层 i 从 0 到 n-1。
- 2内层 j 从 i+1 到 n-1。
- 3若 nums[i] + nums[j] == target，返回 {i, j}。
易错点
- 内层从 0 开始会导致同一个元素被用两次。
- 内层写成 j <= i 会重复检查已经试过的数对。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
nums = [6, -2, 5, 6, 10, 1], target = 12先建立空哈希表。两个 6 是不同下标，不能拿同一个位置用两次。
查看 C++ 代码
延伸阅读
- 「用空间换时间」是哈希类题目的通用套路：把「我见过什么」记下来，后面的元素就不必回头。
- 如果题目改成「返回值本身」且数组有序，可以用双指针做到 O(1) 额外空间。
- 同类变形：三数之和（15）固定一个数后，就退化成本题的双指针版本；和为 K 的子数组（560）把哈希表换成了前缀和。