LeetCode 01. 两数之和 (Two Sum)

题目链接： 1. 两数之和 - 力扣

题目描述

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

思路剖析：为什么选择 HashMap？

我们在遍历数组时，核心诉求是：判断当前元素之前是否已经遍历过某个特定的值。

根据哈希法的常规选型思路（数组 vs Set vs Map）：

  1. 明确查找目标：我们需要寻找的配对数是 所需数 = target - 当前数。
  2. 确定数据结构：如果只需要判断“所需数”是否存在，用 Set 就足够了。但本题要求返回数组下标。
  3. 得出结论：我们需要将**[元素]和[下标]**绑定存储。因此，我们选择用HashMap 。
    • Key (查找目标)：遍历过的元素值。
    • Value (附加信息)：该元素对应的数组下标。

模拟过程

以数组 [1, 3, 7, 5]，target = 8 为例，我们模拟一下代码执行的全过程：

遍历进度 当前元素 (num) 需要寻找的差值 (target - num) HashMap 当前状态 (Key:Value) 操作结果
i = 0 1 8 - 1 = 7 空 Map 里没有 7，把 (1:0) 存入 Map
i = 1 3 8 - 3 = 5 {1:0} Map 里没有 5，把 (3:1) 存入 Map
i = 2 7 8 - 7 = 1 {1:0, 3:1} Map 里存在 1， 它的 Value (下标) 是 0。

得出结论： 存在能与7相加得到target的数，直接返回该元素的下标 0 和当前指针 i 的下标 2，即 [0, 2]。

代码实现

import java.util.HashMap;

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++){
            // 检查哈希表中是否存在能与当前数相加等于 target 的目标数
            if(map.containsKey(target - nums[i])){
                // 若存在，说明配对成功。
                return new int[]{map.get(target - nums[i]), i};
            }
            // 若不存在，将当前数及下标记录到哈希表中，供后面的数进行匹配
            map.put(nums[i], i);
        }
        
        // 题目保证有解，此处为兜底返回，保证方法有确定的返回值
        return new int[0];
    }
}