LeetCode1：两数之和

难度：容易
题目链接：https://leetcode-cn.com/problems/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(n^2)$ 的算法吗？

❖ 循环遍历数组，直观但不高效

看到这个题目时，我们首先想到的方法是从整数数组 nums 中依次取出两个元素，并判断这两个元素的和是否为目标值 target。若是，则直接返回这两个元素的数组下标即可（根据题目描述，我们知道一定存在且仅存在一个这样的有效答案）。

该算法 Java 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
public int[] twoSum(int[] nums, int target) {
    int len = nums.length;

    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[] { i, j };
            }
        }
    }
    return null;
}

该算法比较直观，代码也易于理解，但最大的问题是我们需要遍历数组两次，时间复杂度为 $O(n^2)$，算法的时间效率不是很高。算法的空间复杂度为 $O(1)$。

❖ 使用哈希表保存已经遍历过的数字，用空间换时间的解法

其实，我们可以空间换时间的思想来对上文提到的算法进行优化。在遍历时，我们拿到了元素的值及其对应的数组下标，可以借助哈希表这种数据结构来存储，其中，键（key）为元素的值，值（value）为元素对应的数组下标。

拿到了一个元素的值，用 m 表示，那么从整数数组 nums 中取出一个元素，并且与 m 的和为 target 的问题，就可以转化为：从整数数组 nums 中查找除了 m 以外、并且值为 target - m 的元素。由于在遍历数组的时候，我们可以知道

比如示例 2 中，nums = [3,2,4], target = 6，在第一次遍历时，我们首先拿到元素 3，然后计算 target - m = 6 - 3 = 3，接

1
2
3
4
5
6
7
8
9
10
11
12
13
public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> map = new HashMap<>();

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

        if (map.containsKey(num)) {
            return new int[]{map.get(num), i};
        }
        map.put(nums[i], i);
    }
    return null;
}