题目#

给定一个整数数组 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⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• 只会存在一个有效答案

思考#

首先，看完题目后，根据nums的长度最大为10⁴可以知道，这道题目直接暴力两个for循环判断也是不会超时的。 所以最简单的方法就是暴力两个for直接解决

1
public static int[] twoSum(int[] nums, int target) {
2
    for (int i = 0; i < nums.length - 1; i++) {
3
        for (int j = i + 1; j < nums.length; j++) {
4
            if (nums[i] + nums[j] == target) {
5
                return new int[]{i, j};
6
            }
7
        }
8
    }
9
    return null;
10
}

但是这种方式速度实在太慢了。 接着我想到，内部的for循环其实是在找数组里有没有符合要求的数，那我如果使用一个哈希表，将前面出现过的数的下标存到哈希表中，然后key使用匹配的数(因为是两数之和，所以只有唯一一个匹配的数)，也就是

假如是 nums = [2,7,11,15], target = 9 那么就会是下面这样的流程：

1. 从哈希表中找一下是否存在2需要匹配的数 也就是9-2=7 (目前哈希表为空)
2. 匹配不到 则将 key: 7 (9-2=7) 和value: 0 (2的下标) 存储到哈希表中 (目前哈希表[7-2])
3. 继续遍历下一位，数字7，同样的从哈希表中查找是否存在2 通过map.get(7) 可以得到值 说明存在 且得到的值0就是对应的下标
4. 于是返回 得到的下标 0 和当前的下标 1 返回[0,1]

于是我改成了下面这样的代码：

1
HashMap<Integer, Integer> map = new HashMap<>();
2
for (int i = 0; i < nums.length; i++) {
3
    if(map.containsKey(nums[i])){
4
        return new int[]{map.get(nums[i]),i};
5
    }
6
    map.put(target-nums[i],i);
7
}
8
return null;

总结#

毕竟是简单难度的题目，还是相当轻松就能想到思路的。