【LeetCode 力扣】1.两数之和 Java实现 哈希表

题目链接：1.两数之和

1 原题描述：

2 解题思路

初看题目相信大家都能想到枚举的做法，简单来说把数组里面的所有值，均两两组合相加。若结果与target相等，则将两个数字的下标返回即可。

代码实现1：

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

提交后，虽然能AC,但我们可以发现距离最优解仍然有很长的距离。

同时我们再对我们的代码分析，可以得出我们当前实现代码的时间复杂度为 $O(n^2)$。那我们能不能把时间复杂度优化为 $O(n)$呢。

回看我们的逻辑，我们的本质是为 x 寻找 target - x，那我们现在要做的就是减少 寻找 target - x 的复杂度。对于此目的，我们要采取的方案就是哈希表，先在哈希表中寻找 target - x 是否存在，若存在则直接把 x 和 target - x 的下标返回。若不存在，则将 x 加入哈希表中。

大致逻辑确定了，我们再继续处理一些细节。首先是这个哈希表怎么存储，通过前文分析，我们得知我们需要存储 数字 和 下标，而且我们还要通过 数字 来判断该数字是否存在哈希表中。相信大家已经能想到了，我们要采用的是 HashMap, 其中 key 用来存数字的值，这样我们就可以通过 map.containsKey 来判断该数字是否存在与哈希表中，value 用来存下标，这样返回下标的时候我们可以直接通过 key 获取，而不是再去数组里面找一遍了。

可能又有小伙伴会有这样的疑问，需要判断哈希表里获取的数字的下标是否与我当前 x 的下标一致，若 x = target - x 不判断会不会返回把这一个数字当成两个数字返回呢。其实这是不需要担心的，因为我们在哈希表中寻找 target - x 的时候，并没有将 x 存入哈希表中，所以这时获取的 target - x 一定不是我们当前的 x。

因为我们采用的哈希表， map.containsKey 的时间复杂度为 $O(1)$，那么我们这样实现的整体时间复杂度即为$O(n)$，具体代码实现如下：

代码实现2：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(target - nums[i])) {
                return new int[] {map.get(target-nums[i]),i};
            }
            map.put(nums[i], i);
        }
        return new int[] {0, 0};
    }
}
1
2
3
4
5
6
7
8
9
10
11
12