LeetCode 1. 两数之和
题目描述
✅ 1. 两数之和
题意分析
在整数数组中找到两个不同位置的元素，使它们的和等于
target，返回这两个位置的下标。需要返回的是下标，不是元素值；两数的值可以相同，但不能重复使用同一个位置。题目保证恰好有一组答案，返回下标的顺序不限。数组没有排序，并且原始下标需要保留，因此可以在遍历时直接记录出现过的数及其位置。
解法：一次遍历哈希表
核心思路
[!blue]
固定当前元素
nums[i]后，另一个数必须等于target - nums[i]，称为补数。问题由“枚举所有数对”变成“快速判断需要的补数是否已经出现”，因此用哈希表保存已经遍历过的“数值 → 下标”，用一次查找替代对前面元素的逐个比较。遍历到位置
i时，先查补数。如果表中存在它，就得到一组答案：表里的下标来自当前位置之前，必然与i不同。查不到才将nums[i]和i写入表中，等待后面的元素来配对。先查再存，也保证补数恰好等于当前值时不会把当前元素与自己配对。为什么只查前面的元素就足够？任意一组答案都有先出现和后出现的两个位置；遍历到后者时，前者对应的数值已经被记录，所以这组答案一定会被找到。相同数值再次出现时，可以覆盖旧下标：数值没有改变，保存的位置仍早于后续遍历的位置，因此不会影响之后的合法配对，无需保存所有出现位置。
Java 用查询结果是否为
null判断补数存在与否，Go 用 map 查询返回的ok。不能把下标是否为0当作存在标记，因为下标0本身就是合法答案。题目保证有解，所以找到后可以直接返回，无需继续枚举。
解题步骤
- 创建空哈希表
indexByValue。- 遍历数组，计算补数
need = target - nums[i]。- 若补数已在表中，返回补数下标和当前下标。
- 否则记录当前值及其下标，继续遍历。
代码实现
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> indexByValue = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
// 表中只有当前下标之前的元素，命中时不会复用自身。
Integer j = indexByValue.get(need);
if (j != null) {
return new int[] {
j,
i,
};
}
// 先查补数再记录当前值，两个相同值也能正确配对。
indexByValue.put(nums[i], i);
}
return new int[0];
}
}
func twoSum(nums []int, target int) []int {
indexByValue := make(map[int]int)
for i, num := range nums {
need := target - num
// 表中只有当前下标之前的元素，命中时不会复用自身。
if j, ok := indexByValue[need]; ok {
return []int{
j,
i,
}
}
// 先查补数再记录当前值，两个相同值也能正确配对。
indexByValue[num] = i
}
return []int{}
}
复杂度分析
- 时间复杂度：平均 $O(n)$，每个元素至多查询、写入哈希表一次，单次哈希表操作平均为 $O(1)$。
- 空间复杂度：$O(n)$，哈希表最多保存 $n$ 个元素。
关键点总结
[!green]
- 哈希表保存下标，而不是只记录元素是否存在。
- 先查补数、后存当前值，既避免复用当前元素，也能正确处理重复值。
- 命中即返回，无需继续遍历或额外排序。
易错点总结
[!yellow]
- 先存当前值再查补数，可能把同一元素使用两次。
- 哈希表只存元素、不存下标，无法构造返回值。
- 把重复值丢弃后再处理，会漏掉由两个相同数值组成的答案。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 167. 两数之和 II - 输入有序数组 | 中等 | 数组有序后可用两端指针寻找互补值，本题无序时用哈希表记录已见元素。 |
| 15. 三数之和 | 中等 | 固定一个元素后转成两数之和，额外处理三元组去重。 |
| 170. 两数之和 III - 数据结构设计 | 简单 | 用哈希表查询当前元素所需的补值；本题查找一个目标和下标对，该题把补值查询扩展为多次动态查询。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！