LeetCode 1 两数之和 Java 解法：暴力枚举与 HashMap

给定整数数组 nums 和目标值 target，找出和为目标值的两个元素，并返回它们的数组下标。同一个元素不能重复使用。

示例

输入：nums = [2, 7, 11, 15], target = 9
输出：[0, 1]
解释：nums[0] + nums[1] = 2 + 7 = 9

解法一：双重循环

最直接的方法是枚举所有不同的元素组合：

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("No solution");
    }
}

内层循环从 i + 1 开始，既避免重复比较，也保证不会重复使用同一个元素。

复杂度：

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$

解法二：HashMap 一次遍历

遍历到 nums[i] 时，需要查找的另一个数是：

$$ complement = target - nums[i] $$

使用 HashMap 保存已经遍历过的“数值 → 下标”：

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> indexByValue = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];

            if (indexByValue.containsKey(complement)) {
                return new int[] {
                    indexByValue.get(complement),
                    i
                };
            }

            indexByValue.put(nums[i], i);
        }

        throw new IllegalArgumentException("No solution");
    }
}

复杂度：

• 平均时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

为什么先查找再存入

假设输入为：

nums = [3, 3], target = 6

第一次遇到 3 时，Map 中还没有另一个 3，于是记录下标 0。第二次遇到 3 时即可返回 [0, 1]。

如果先存入再查找，可能错误地把当前元素与自己匹配。

重复数字如何处理

Map 中相同数值的下标可能被后面的元素覆盖，但题目只要求返回一组答案。由于每轮都会先查找 complement，遇到可行组合时已经立即返回，因此不会影响正确性。

两种方法如何选择

• 学习枚举思想或数组较短时，双重循环更直观。
• 数据规模较大时，HashMap 将时间复杂度从 $O(n^2)$ 降到平均 $O(n)$。
• 面试中建议先说明暴力解法，再给出 HashMap 优化过程。