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

---

两数之和

题目解析

---

思路

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

• 时间复杂度 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};}
};