【算法 - 哈希表】两数之和

两数之和

题目解析

思路

解法一 ：暴力枚举 依次遍历

• 时间复杂度 O(n^2)
  暴力枚举两层for()循环遍历O(n^2)
• 空间复杂度 无

1. 先固定其中一个数
2. 依次与该数之前的数相加

而 解法二 则是，遍历完这个数以后，将其丢入hash表中。枚举下一个数时，很自然的枚举hash表中前面遍历过的数

解法二 ：使用哈希表来做优化

• 时间复杂度：O(n)
  由原来的 暴力枚举两层for()循环遍历O(n^2) 到 ，只需遍历一遍 固定一个数O(n)，哈希表查找匹配的另一个数O(1)

• 空间复杂度：O(n)
  对比 暴力枚举 即可看出，哈希表是用 空间换时间

核心逻辑

为什么之前的暴力枚举策略不太好用了？

我们也能把所有的数都放入hash表中，再由前往后遍历一遍数组，再直接在hash中找匹配的数就好了，为什么还要 逐一遍历，再将遍历到的节点逐一放入hash表中 ？

这是因为会出现 “恰好 遍历到的数本身，也能满足匹配的要求” 的情况，这违反了题目所说的需求 数组中同一个元素在答案里不能重复出现

blog.csdnimg.cn/direct/4e384c8f2ebd454f910606e12c610d2c.jpeg)

因此，这种做法需要加入特判。

所以，这就是 这道题选择 固定一个数，再与其前面的数逐一对比完后，再将其自身放入hash表中，参与匹配 的原因

因此，循环遍历固定一个节点，遍历完后将该节点放入hash表中，后继续向后遍历，仅需查找前面放入hash表中的值即可（就不会出现查找hash表中选中自身的情况），这样的顺序避免了 出现了重复出现同一个数字 的情况 。也 不需要再处理什么边界情况 了。

代码实现

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {                                   //  数  ，下标
        unordered_map<int,int> hash;    // <nums[i],i>   

        // 遍历数组
        for(int i=0;i<nums.size();i++)
        {
            int x=target-nums[i];
            if(hash.count(x)) return {hash[x],i};  // hash[x]中 存放的就是 x的下标
            hash[nums[i]]=i;     // 遍历完后，将该节点放入到hash表中
        }

        // 照顾编译器
        return {1,-1};
    }
};