0001. 两数之和 #

标签：数学
难度：简单

一、题目说明 #

描述：给定一个整数数组 nums 和一个整数目标值 target。

要求：在该数组中找出和为 target 的两个整数，并输出这两个整数的下标。可以按任意顺序返回答案。

说明：

$2 \le nums.length \le 10^4$。
$-10^9 \le nums[i] \le 10^9$。
$-10^9 \le target \le 10^9$。
只会存在一个有效答案。

示例：

示例 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]

二、解题思路 #

1. 暴力破解 #

首先有一点可以肯定：寻找整数数组nums中的某个或者某几个元素，必然需要通过下标来访问，那么，对数组进行遍历是一个必要的操作。
假设这个数组中有两个元素的下标分别是i和j，正好满足nums[i] + nums[j] == target ，那么我就可以说，i和j就是要寻找的答案。
那么按照朴素的思维方式，如果能够将数组nums中所有的元素都两两求和，那么最终一定能找到结果。
为了找到索引i和j，需要进行两层遍历：
1. 首先假设外层遍历的索引为i，它需要从索引0开始，一直遍历到数组的最后一个元素，即nums[nums.length - 1]；
2. 在外层的遍历过程中，每次都能确定索引i的位置，然后将索引i后面的元素依次与其相加，并判断是否等于target；
```
for(int i=0;i<nums.length-1;i++){
    for(int j=i+1;j<nums.length;j++){
        if(nums[i] + nums[j] == target){
            //i和j即为所求
        }
    }
}
```
全量的代码如下：
```
public int[] twoSum(int[] nums, int target) {
    for(int i=0;i<nums.length-1;i++){
        for(int j=i+1;j<nums.length;j++){
            if(nums[i] + nums[j] == target){
                return new int[]{i,j};
            }
        }
    }
    return null;
}
```
当然，这属于一种暴力破解的方式。其核心逻辑在于，对数组中的元素进行数学逻辑上的组合，以穷尽遍历的方式找到符合要求的数据。

其中，用到的变量只有固定的i和j，所以空间复杂度为：$O(1)$。

由于采用的是循环嵌套循环的方式，所以时间复杂度为：$O(n^2)$。

2. 边缓存，边遍历 #

对于上面的暴力破解而言，由于是for循环嵌套for循环的方式，故而时间复杂度不太理想。通过观察其流程可以发现，数组nums中有很多元素，被反复访问了多次，如果将已访问的元素，以集合的形式存储起来，那么只需要从这个集合中去找就可以了，从而避免了元素被重复访问的问题。

确定了这一点之后，下一步就需要考虑，用哪一种集合来存储已经访问过的元素。由题意可知，我们需要找到两个元素，这两个元素之和等于目标值，然后将这两个元素的下标返回。所以，这个集合需要存储元素值，也需要存储该元素对应的数组下标，即map。

public int[] twoSum(int[] nums, int target){
    //key是数组的元素,value是数组索引下标
    Map<Integer, Integer> map = new HashMap<>();
    for(int i=0;i<nums.length;i++){
        if(map.containsKey(target - nums[i])){
            return new int[]{i, map.get(target - nums[i])};
        }else{
            map.put(nums[i], i);
        }
    }
    return null;
}