Two Sum 是一道非常经典的入门算法题。
给定一个整数数组 nums 和一个目标值 target，请在数组中找出 和为目标值 的那两个整数，并返回它们的数组下标。
题目示例
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
因为 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0,1]。
一、暴力枚举
最直接的想法就是枚举所有可能的两个数，判断它们的和是否等于 target。
代码
class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
throw new IllegalArgumentException("没有找到");
}
}
思路分析
-
外层循环固定第一个数
nums[i] -
内层循环寻找第二个数
nums[j] -
如果
nums[i] + nums[j] == target，直接返回两个下标
复杂度分析
-
时间复杂度：
O(n^2) -
空间复杂度：
O(1)
这种写法思路清晰，但效率较低。当数组很大时，会做很多重复比较。
二、HashMap 优化
优化的核心思想是：
当遍历到当前元素 nums[i] 时，先判断 target - nums[i] 是否已经在前面出现过。
如果出现过，说明已经找到了答案。
因此，我们可以使用 HashMap 来记录已经遍历过的元素。
正确的 HashMap 记录方式
这里需要注意：
-
key：数组元素的值 -
value：该元素对应的下标
也就是说：
map.put(nums[i], i);
而不是“索引作为 key，元素作为 value”。
优化代码
import java.util.HashMap;
import java.util.Map;
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int x = target - nums[i];
if (map.containsKey(x)) {
return new int[]{map.get(x), i};
}
// 把当前值和下标存入 map
map.put(nums[i], i);
}
throw new IllegalArgumentException("没找到");
}
}
思路拆解
假设：
nums = [2,7,11,15], target = 9
遍历过程如下：
第 1 轮
-
当前元素：
2 -
需要寻找的值：
9 - 2 = 7 -
map中没有7 -
存入
map：{2:0}
第 2 轮
-
当前元素：
7 -
需要寻找的值：
9 - 7 = 2 -
map中存在2 -
返回结果：
[0,1]
这样只需要遍历一遍数组，就能找到答案。
为什么这样做更快？
暴力解法需要两层循环，本质上是在不断尝试所有配对。
而使用 HashMap 后，我们可以把“查找另一个数是否存在”这件事优化到接近常数时间。
因此整体效率从：
-
暴力枚举：
O(n^2)
优化为：
-
哈希表：
O(n)
复杂度分析
时间复杂度
-
O(n)
数组只遍历一次，每次 HashMap 查询和插入的平均时间复杂度都是 O(1)。
空间复杂度
-
O(n)
最坏情况下，数组中的所有元素都会被存进 HashMap
所以空间复杂度不是
Max{nums[i]}，而是和存入哈希表的元素个数有关，即O(n)。
总结
这道题体现了一个非常重要的算法思想：
用空间换时间。
-
暴力解法：实现简单，但效率低
-
HashMap优化：多使用了额外空间，但把时间复杂度降到了O(n)
对于 Two Sum 这类“边遍历边查找”的问题，哈希表通常都是非常自然的优化方式。
适合直接发布的结尾
如果你刚开始刷算法，这道题非常值得反复体会：
-
先写出暴力解法，保证正确性
-
再思考哪些重复操作可以优化
-
最后引入合适的数据结构（如
HashMap）
