LC1. 两数之和

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。

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

提示： 2 <= nums.length <= 10(4) -10(9) <= nums[i] <= 10(9) -10(9) <= target <= 10(9) 只会存在一个有效答案

题目解析

题目在说什么

简单来说，题目给了你一个数组（比如 [2, 7, 11, 15]）和一个目标数字（比如 9）。你要在数组里找到两个数，让它们加起来等于 9。然后，把这两个数在数组里的位置（也就是下标）返回出来。注意，同一个数不能用两次，而且题目保证只有一组答案。

比如 [2, 7, 11, 15] 里，2 和 7 加起来是 9，它们的位置分别是 0 和 1，所以返回 [0, 1]。

思路是怎么来的

想象一下，你在一堆卡片里找两张牌，这两张牌的点数加起来正好等于某个数。最笨的办法是：先拿第一张牌，然后一张一张看后面的牌，看有没有能和它配对的。但这样太慢了，如果牌很多，你得翻很多次。

那有没有更聪明的办法？你可以这样做：每拿起一张牌，就记下它的点数，然后心里想：“我需要另一张牌，它的点数等于目标数减去我这张牌的点数。” 比如目标数是 9，你拿起 2，你就知道你需要 7。然后你回头看看之前记下的牌里有没有 7。如果有，就找到了；如果没有，就把 2 记下来，继续看下一张牌。

这样，你只需要从头到尾看一遍牌，每次只看当前这张牌，同时检查之前记下的牌里有没有需要的。这就是“一次遍历 + 哈希表”的思路。哈希表就像你的记忆本，能快速告诉你某个数之前有没有出现过。

代码逐步拆解

我们来看参考代码，一行一行解释它在干什么。

Map<Integer, Integer> map = new HashMap<>();

• 这一行创建了一个“哈希表”，名字叫 map。它就像一个本子，专门用来记“数字”和“这个数字在数组里的位置”。比如，如果数组第一个数是 2，位置是 0，我们就在本子上写：2 -> 0。

for (int i = 0; i < nums.length; i++) {

• 这是一个循环，从数组的第一个元素（下标 0）开始，一直走到最后一个元素。i 就是当前元素的下标。

    int anotherNum = target - nums[i];

• 对于当前这个数 nums[i]，我们计算它需要和谁配对才能得到 target。比如 target = 9，当前数是 2，那么 anotherNum = 9 - 2 = 7。也就是说，我们需要找 7。

    if (map.containsKey(anotherNum)) {

• 这句检查我们的“记忆本”里有没有记过 7。如果有，说明之前已经遇到过 7 了，那 7 和当前的 2 正好配对。

        return new int[]{ map.get(anotherNum), i };

• 如果找到了，就返回两个下标：一个是 7 的下标（从本子里查出来），一个是当前数 2 的下标 i。注意顺序：先返回之前那个数的下标，再返回当前的下标。

    map.put(nums[i], i);