题解 | #两数之和#

题目主要信息:

题目给出的是一个数组和一个目标值，需要我们在数组中找到两个加起来等于目标值的数组元素的下标
下标按升序排列，从1开始

举一反三：

学习完本题的思路你可以解决如下题目：

BM54. 三数之和

方法：哈希表（推荐使用）

知识点：哈希表

哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在 $O (1)$ 时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。

思路：

我们能想到最直观的解法，可能就是两层遍历，将数组所有的二元组合枚举一遍，看看是否是和为目标值，但是这样太费时间了，既然加法这么复杂，我们是不是可以尝试一下减法：对于数组中出现的一个数a，如果目标值减去a的值已经出现过了，那这不就是我们要找的一对元组吗？这种时候，快速找到已经出现过的某个值，可以考虑使用哈希表快速检验某个元素是否出现过这一功能。

具体做法：

step 1：构建一个哈希表，其中key值为遍历数组过程中出现过的值，value值为其相应的下标，因为我们最终要返回的是下标。
step 2：遍历数组每个元素，如果目标值减去该元素的结果在哈希表中存在，说明我们先前遍历的时候它出现过，根据记录的下标，就可以得到结果。
step 3：如果相减后的结果没有在哈希表中，说明先前遍历的元素中没有它对应的另一个值，那我们将它加入哈希表，等待后续它匹配的那个值出现即可。
step 4：需要注意最后的结果是下标值加1.

图示：

alt

Java实现代码：

import java.util.*;
public class Solution {
    public int[] twoSum (int[] numbers, int target) {
        int[] res = new int[0];
        //创建哈希表,两元组分别表示值、下标
        HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>(); 
        //在哈希表中查找target-numbers[i]
        for(int i = 0; i < numbers.length; i++){
            int temp = target - numbers[i];
            //若是没找到，将此信息计入哈希表
            if(!hash.containsKey(temp)) 
                hash.put(numbers[i], i);
            //否则返回两个下标+1
            else 
                return new int[] {hash.get(temp) + 1, i + 1}; 
        }
        return res;
    }
}

C++实现代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> res;
        //创建哈希表,两元组分别表示值、下标
        unordered_map<int, int> hash; 
        //在哈希表中查找target-numbers[i]
        for(int i = 0; i < numbers.size(); i++){
            int temp = target - numbers[i];
            //若是没找到，将此信息计入哈希表
            if(hash.find(temp) == hash.end()){ 
                hash[numbers[i]] = i;
            }
            else{
                //哈希表中记录的是之前的数字，所以该索引比当前小
                res.push_back(hash[temp] + 1);   
                res.push_back(i + 1);
                break;
            }
        }
        return res;
    }
};

Python实现代码

class Solution:
    def twoSum(self , numbers: List[int], target: int) -> List[int]:
        res = []
        #创建哈希表,两元组分别表示值、下标
        hash = dict() 
        #在哈希表中查找target-numbers[i]
        for i in range(len(numbers)) :
            temp = target - numbers[i]
            #若是没找到，将此信息计入哈希表
            if temp not in hash: 
                hash[numbers[i]] = i
            else:
                #哈希表中记录的是之前的数字，所以该索引比当前小
                res.append(hash[temp] + 1) 
                res.append(i + 1)
                break
        return res

复杂度分析：

时间复杂度： $O (n)$ ，仅仅遍历数组一次，每次查询哈希表都是 $O (1)$
空间复杂度： $O (n)$ ，最坏情况下找到数组结尾才找到，其他都加入哈希表，因此哈希表最长为 $n - 1$ 的长度