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 <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

进阶： 你可以想出一个时间复杂度小于 O(n^2) 的算法吗？

解题思路

暴力的做法是：双重循环，遍历所有的元素，看相加结果是否等于目标值，碰到符合要求的元素返回其索引。

但这种做法时间复杂度为 O(n^2)，感觉很不优雅。

我们换个理解方式，第二层 for 循环无非就是遍历所有的元素，看哪个元素等于 target - num[i]，时间复杂度为 O(n)。

有没有一种方法，不用遍历就可以快速找到数组里有没有元素值等于 target - num[i] ？

答案是 HashMap。

我们可以把数组的每个元素保存为 map 的 key，其数组下标保存为 value 。

这样只需判断 target - num[i] 在不在 map 的 key 里就可以了，而这样做的时间复杂度仅为 O(1)。

我的思路：

设定一个哈希表 map，初始为空
遍历数组 nums，设定当前元素为 one，目标元素为 two
判断 map 里是否已经存在目标元素 two
- 若存在，则返回当前元素下标和目标元素下标
- 若不存在，则将当前元素存入 map

注意，这里往 map 中添加元素放在了循环内最后一步，因为数组中同一个元素在答案里不能重复使用，如示例 2，如果一开始就把当前元素放进 map，那么示例2 返回的结果将会是 [0,0]，因为当前元素和目标元素值相同了

我的代码

java

public int[] twoSum(int[] nums, int target) {
    // 创建一个HashMap来存储数组元素和它们的索引
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < nums.length; i++) {
        int one = nums[i];
        int two = target - one;// 计算目标值与当前元素的差
        // 检查差值是否已在Map中
        if (map.containsKey(two)) {
            // 如果差值存在，返回当前索引和差值的索引
            return new int[]{i, map.get(two)};
        }
        // 将当前元素和它的索引存储在Map中
        map.put(nums[i], i);
    }
    // 如果没有找到这样的两个数，则返回null
    return null;
}

时间复杂度：O(n)

空间复杂度：所谓的 空间换时间，这里就能体现出来，开辟了一个 HashMap ，空间复杂度变为 O(n)

总结

什么时候使用哈希法：

当我们需要快速查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

本题，我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value 结构来存放，key 来存元素，value 来存下标，那么使用 map 正合适。

使用数组和 set 来做哈希法的局限：

数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set 是一个集合，里面放的元素只能是一个 key，而本题，不仅要判断 y 是否存在而且还要记录 y 的下标位置，因为要返回 x 和 y 的下标。所以 set 也不能用。

1.两数之和 ​

解题思路 ​

我的代码 ​

总结 ​

1.两数之和

解题思路

我的代码

总结