每日一题 - LeetCode 热题 HOT 100 - 1. 两数之和

1. 题目

给定一个整数数组 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$$

只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

2.思路一

这个题目在LeetCode属于简单题目，我想应该是因为可以暴力输出，所以标记为简单。我们大多数人应该首先想到的也是暴力破解，简要贴上我的暴力循环代码

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++){ //这里j如果从0开始，有可能出现返回同一个下标值的情况，比如[3,3],6的时候，会返回00
                if (nums[i] + nums[j] == target){
                    return new int[]{i,j};
                }
            }
        }
        return new int[0];
    }
}

这种暴力代码每个人都会解，没有什么难度。但最终的$O(n^2)$的时间复杂度并不能解决任何实际问题。

3.思路二（进阶）

上述暴力解法肯定不是最优策略，其实我们仔细看一下题目，就知道给定了target，需要去找两个匹配值。由于这个数组nums中只会存在一个有效答案，那么我们可以使用HashMap的方式。假设这两个数分别是num1和num2，那么num1=target-num2是唯一成立的。我们可以将target-num1作为key，将num1作为value，那么在循环一次的时候，只需要判断当前HashMap有没有包含当前循环值，如果包含了，那就是存在一个num2使得num1=target-num2。根据这个思路，编写代码如下：

import java.util.HashMap;
import java.util.Map;
class Solution {
    public int[] twoSum(int[] nums, int target) {
       HashMap<Integer, Integer> map = new HashMap(); //空间换时间
       for (int i =0;i<nums.length;i++){
           if(map.containsKey(nums[i])){
               return new int[]{i, map.get(nums[i])};
           }
           map.put(target-nums[i], i);
       }
       return new int[0];
    }
}

4.总结

HashMap在经典算法结构中用处很多，需要多多练习。

参考

1. LeetCode 热题 HOT 100 https://leetcode.cn/problem-list/2cktkvj/
2. 两数之和 https://leetcode.cn/problems/two-sum/