两数之和
这是一道围绕数组、哈希表展开的高频练习。建议先掌握「哈希表优化」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
题目分析
给你一个整数数组和一个目标值 target。
要求你找到两个下标，使这两个位置上的数字相加正好等于 target，并返回这两个下标。
题目保证答案唯一，而且同一个元素不能重复使用。
一句话概括：
一边遍历数组，一边寻找当前数字所需要的配对值。
推荐代码
class Solution {
/**
* 哈希表优化解法
* 使用HashMap存储已遍历的元素，实现O(n)时间复杂度
*/
public int[] twoSum(int[] nums, int target) {
// hashtable的key为数组的值，value为数组的下标
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
}结构化讲解
面试时怎么讲
开场思路
这题我会把它看成“遍历当前数字时，快速找出它缺的那一半”，所以最自然的做法是哈希表。
核心过程
- 遍历到
nums[i]时，先计算补数need = target - nums[i]。 - 去哈希表里查询
need是否已经出现过；如果出现过，就直接返回之前的下标和当前位置。 - 如果没查到，再把当前值和下标写进哈希表，继续往后处理。
复杂度总结
时间复杂度 O(n)，空间复杂度 O(n)。
核心思路
一边遍历数组，一边把“已经看过的值 -> 下标”存进哈希表。当前元素只需要查一次补数是否已出现过。
步骤讲解
先算补数
遍历到 nums[i] 时，先计算当前数字还缺什么值才能凑成 target。
查哈希表
去哈希表里查 need 是否已经在左侧出现过。
命中就返回答案
如果补数存在，直接返回哈希表里的旧下标和当前下标。
未命中再入表
如果当前补数不存在，再把当前值和下标写入哈希表。
易错点
必须先查后存
如果先把当前元素写进哈希表，再查补数，就可能在 target = 2 * nums[i] 时错误地让当前元素和自己配对。
哈希表里存的是值到下标
很多人会只记“用哈希表优化”，但忘了为什么要存下标。题目最后要求返回的是两个位置，而不是两个值。
值 -> 下标，命中时才能直接返回答案。复杂度与适用判断
额外提醒
- 把“找另一半”的问题变成哈希查找，是这道题最关键的优化点。
- 动画里最重要的不是 map 长什么样，而是先算补数、再查表、最后决定是否入表。
其他语言 / 其他解法
暴力解法
按顺序枚举每一对不同下标 (i, j)，只要这两个位置的和等于 target 就立即返回。
暴力解法
按顺序枚举每一对不同下标 (i, j)，只要这两个位置的和等于 target 就立即返回。
class Solution {
/**
* 暴力解法
* 枚举所有可能的两数组合，时间复杂度O(n²)
*/
public int[] twoSum(int[] nums, int target) {
if (nums == null) {
return null;
}
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) {
result[0] = i;
for (int j = i + 1; j < nums.length; j++) {
result[1] = j;
if (nums[result[0]] + nums[result[1]] == target) {
return result;
}
}
}
return result;
}
}动画演示
如果你还没完全看懂，可以展开动画演示。
哈希表优化动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
哈希表优化动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪：哈希法会先算补数，再查表，最后决定是否入表。
当前阶段
等待处理下一个元素
补数
尚未计算
统计
已处理 0 个元素，查表 0 次
最近动作
等待开始
哈希表快照
当前为空
暴力解法动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
暴力解法动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪：暴力法会按顺序枚举每一对下标。
当前配对
尚未开始
枚举进度
0 / 6 对
最近检查
尚无