两数之和（哈希解法）

题目描述

给定一个整数数组 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
• 只会存在一个有效答案

题解

我们首先来看暴力解法：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i=0;isize();i++)
        {
            for(int j=i+1;jsize();j++)
            {
                if(nums[i]+nums[j]==target)
                    return {i,j};
            }
        }
        return {};
    }
};

在暴力解法中，我们先固定一个指针i指向nums中的一个元素，之后使用指针j遍历其后的每一个元素，判断nums[i]+nums[j]是否等于target，事实上，我们对nums[j]的枚举其实等价于是否存在一个数使得该数的值等于target-num[i]

即，对于第二层for循环nums[j]的枚举其实是在寻找值为target-nums[i]的数

明白暴力解法的逻辑，我们就可以对第二层for循环进行优化，试想，如果我们有一个与nums相同的数组mp，之后我们在第一层for循环指针i遍历nums时，直接在mp中寻找是否存在一个数的值等于target-nums[i]，而不是挨个遍历去寻找，也就是说让在mp中寻找值的时间优于遍历的时间O（n）即可，如果存在这样一个值，我们就找到了符合条件的两数，而题目中要求的是求出这两数的下标，因此我们还需要在mp中记录每个数对应的下标，符合该条件的数据结构显然是unordered_map，而刚好在unordered_map中查找一个数的时间复杂度是O（1），显然O（1）的时间复杂度要优于第二层for循环O（n）的复杂度

伪代码是：

for(int i=0;isize();i++)//在nums中固定nums[i]
{
    if(nums.find(target-nums[i])!=mp.end())
    //在mp数组中寻找是否存在target-nums[i]，该查找的时间复杂度是O（1）
    {
        //找到结果
    }
}

构建一个哈希表mp，key存放nums的元素，value存放对应元素的下标，遍历数组nums，用mp存放遍历过的元素，并在哈希表中寻找target-nums[i]，如果找到，并返回指向target-nums[i]的迭代器iter，说明iter->second与当前的i就是我们寻找的数对，否则就将nums[i]及其对应的下标存放到mp中

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> mp;
        for(int i=0;isize();i++)
        {
            auto iter=mp.find(target-nums[i]);
            if(iter!=mp.end())
                return {iter->second,i};
            mp.insert({nums[i],i});
        }
        return {};
    }
};