【Hot100-Java简单】：两数之和 (Two Sum) —— 从暴力枚举到哈希表的思维跃迁
1. 题目回顾
题目描述：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
约束条件：
每种输入只会对应一个答案。
数组中同一个元素在答案里不能重复出现。
可以按任意顺序返回答案。
示例：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。2. 方法一：暴力枚举 (Brute Force)
这是最直观的解题思路。这就好比我们在一个房间里找两个人，我们先拉住第1个人，然后去问剩下的所有人：“你是那个能和我配对的人吗？”如果不是，再拉住第2个人，重复这个过程。
思路与算法
枚举数组中的每一个数
x（作为第一个加数）。在
x后面的元素中，寻找是否存在target - x（作为第二个加数）。一旦找到，立即返回两个数的下标。
代码实现
Java
class Solution { public int[] twoSum(int[] nums, int target) { int n = nums.length; // 第一层循环：选定第一个数 for (int i = 0; i < n; ++i) { // 第二层循环：在 i 之后寻找第二个数 for (int j = i + 1; j < n; ++j) { if (nums[i] + nums[j] == target) { return new int[]{i, j}; } } } return new int[0]; } }复杂度分析
时间复杂度：
其中
是数组元素的数量。最坏情况下，我们需要遍历几乎所有的元素对。当数据量较大（例如
）时，计算量会达到 1亿次级别，效率较低。
空间复杂度：
。
除了存储变量，不需要额外的内存空间。
3. 方法二：哈希表 (Hash Map) —— 性能的飞跃
暴力法慢在哪里？慢在“寻找”。
我们在数组中寻找 target - x 时，不得不遍历整个后续数组，这需要 $O(N)$ 的时间。如果我们能把“寻找”的时间缩短到呢？
这就需要用到哈希表 (Hash Map)。
思路与算法
我们可以把哈希表想象成一个“备忘录”。
在遍历数组时，对于每一个数 nums[i]：
我们先算一下：为了凑齐
target，我需要哪个数？（即need = target - nums[i]）。查备忘录：看看之前遍历过的数字里，有没有这个
need？如果就在备忘录里：太好了，说明之前遇到过那个数，直接把它的下标拿出来，和当前的
i一起返回。如果不在：把当前的数
nums[i]和它的下标i记入备忘录，方便后面的数字来找我匹配。
代码实现
Java
class Solution { public int[] twoSum(int[] nums, int target) { // Key存数值，Value存下标 HashMap<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < nums.length; i++){ int need = target - nums[i]; // 查备忘录：看需要的那个数是否存在 if(map.containsKey(need)){ // 找到了！直接返回 [需要的数的下标, 当前数的下标] return new int[]{map.get(need), i}; } // 没找到，把自己登记到备忘录 map.put(nums[i], i); } return new int[0]; } }复杂度分析
时间复杂度：
。
我们只需要遍历一次数组。在哈希表中查找元素的时间复杂度平均为 $O(1)$。
空间复杂度：
。
我们需要一个哈希表来存储已经遍历过的元素，最坏情况下需要存储 $N$ 个元素。
4. 总结与对比
| 特性 | 暴力枚举法 | 哈希表法 |
| 核心思想 | 穷举所有组合 | 边查边存（以空间换时间） |
| 时间复杂度 | ||
| 空间复杂度 | ||
| 适用场景 | 数据量极小，内存极其受限 | 通用场景，追求运行速度 |