（LeetCodeHot100）1. 两数之和——two-sum

zhangzhang2025-11-102025-11-10

1. 两数之和——two-sum

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

1
2
3

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

1 2	输入：nums = [3,2,4], target = 6 输出：[1,2]

示例 3：

1 2	输入：nums = [3,3], target = 6 输出：[0,1]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

**进阶：**你可以想出一个时间复杂度小于 O(n2) 的算法吗？

法一：暴力枚举（我的答案）

思路及算法

最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x。

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                // 如果匹配到了就直接返回
                if (nums[i] + nums[j] == target) {
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        return new int[0];
    }
}

1.return result

可以直接返回 result 数组名，因为在 Java 中，数组名本质上是引用变量，指向数组在内存中的地址。返回数组名时，实际返回的是这个引用，调用者可以通过该引用访问数组中的元素。

2.return new int[]{i, j};

这是创建一个匿名的 int 类型数组，并直接初始化元素值为 i 和 j。

new int[] 声明创建一个 int 数组（方括号中不写长度，因为编译器可通过初始化元素数量自动推断长度为 2）。
{i, j} 是数组的初始化列表，为数组的两个元素赋值（索引 0 为 i，索引 1 为 j）。

复杂度分析

时间复杂度：O(N2)，其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
空间复杂度：O(1)。

法二：哈希表

思路及算法

注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。

这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        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];
    }
}

复杂度分析

时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。
空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。

详解

就是取每一个数（假如target是9，当前取的是2），看需要的数（7）在不在哈希表里面

class Solution {
    // 方法定义：输入int数组nums和目标值target，返回两个元素的索引数组
    public int[] twoSum(int[] nums, int target) {
        // 1. 创建哈希表：key存数组元素值，value存该元素的索引
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        
        // 2. 遍历数组，索引i从0到nums.length-1
        for (int i = 0; i < nums.length; ++i) {
            // 3. 计算“与当前元素nums[i]配对的目标值”：complement = target - nums[i]
            // 检查哈希表中是否存在这个目标值（即是否有之前的元素能与当前元素凑成target）
            if (hashtable.containsKey(target - nums[i])) {
                // 4. 若存在，直接返回两个索引：
                //    - 哈希表中目标值对应的索引（之前存入的元素索引）
                //    - 当前元素的索引i
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            // 5. 若不存在，将当前元素的值和索引存入哈希表，供后续元素查找
            hashtable.put(nums[i], i);
        }
        // 6. 若遍历完数组仍未找到（题目假设一定有解，此行为兜底）
        return new int[0];
    }
}

举例说明

（以 nums = [2,7,11,15], target = 9 为例）

i=0：当前元素 nums[0]=2，目标值 9-2=7。哈希表为空（无 7），将 (2,0) 存入哈希表。
i=1：当前元素 nums[1]=7，目标值 9-7=2。哈希表中存在 2（对应索引 0），因此返回 [0,1]，程序结束。

细节

一、值和索引的关系（核心映射）

在这道题中，HashMap 存储的是 “数组元素的值 → 该元素在数组中的索引” 的映射关系：

Key（键）：数组里的具体元素值（如 nums[i]，比如 2、7、11 等）；
Value（值）：这个元素在数组中的位置（即索引 i，比如 2 对应索引 0，7 对应索引 1）。

简单说：通过元素值（Key），能快速找到它在数组里的位置（Value），就像 “查字典”—— 用汉字（Key）查页码（Value）。

二、`containsKey` 和 `get` 的返回值

1. `hashtable.containsKey(target - nums[i])`

作用：判断哈希表中是否存在某个 Key（即 “目标元素值”）；
返回值：boolean类型（true 或false）；
- 存在该 Key → 返回 true（说明之前遍历过的元素里有能和当前元素凑成 target 的）；
- 不存在该 Key → 返回 false（说明还没找到配对元素）。

2. `hashtable.get(target - nums[i])`

作用：根据指定的 Key（目标元素值），获取对应的 Value（该元素的索引）；
返回值：Integer类型（即之前存入的索引值）；
- 若 Key 存在 → 返回该 Key 对应的索引（比如 Key 是 2，返回 0）；
- 若 Key 不存在 → 返回 null（但本题中，get 只在 containsKey 返回 true 后调用，所以一定能拿到索引）。