leetcode 1. 两数之和（哈希表）

Dear 丶 2023-09-26 11:33 8阅读 0赞

> ![在这里插入图片描述][38595e5e2f5e466ea2a00319e7cd7dd9.png]  
> ![在这里插入图片描述][31f0f38657224214bef335fdc6c81bd6.png]  
> 评论真的笑死了，忍不住了

给定一个整数数组 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) {
        
            unordered_map<int,int> hashtable;
            int n=nums.size();
            for(int i=0;i<n;++i){
        
                auto it=hashtable.find(target-nums[i]);
                if(it!=hashtable.end())//迭代器没有走到最后说明在中间的位置就找到了，所以可以直接返回
                    return {
        i,hashtable[target-nums[i]]};
                hashtable[nums[i]]=i;
            }
            return {
        };
        }
    };

> unordered\_map的内部时用哈希表实现的，内部元素无序杂乱。

代码思路：  
一开始就在哈希表中找是否有 target-nums\[i\] 的元素，如果有，也就是迭代器没有走到最后，那么直接返回当前下标和哈希表中键值为 target-nums\[i\] 的value值，也就是 target-nums\[i\] 的下标；如果没有找到，那就说明在这个数之前是没有和它匹配的，可能与之匹配的在后面，所以要先存到哈希表中，便于后面元素寻找。

> 哈希表中 unordered\_map<int,int> 的第一个int是键值key，第二个int是value值。  
>   
> 
> 
> 可以 hashmap\[x\]=y 这样使用哈希表的值，x即代表键值，y是x对应的value值。  
> 在这个函数中用key值保存数组中的值，value保存对应的下标值。

假设nums中元素顺序为 \{2,11,7,.15\}  
i=0时，一开始是2，9-2=7 并不在哈希表里面，所以将\{2,0\}加入到哈希表中。这说明在2之前是没有值和它相加等于9，然后继续向后找。  
i=1时，9-11=-2也不在哈希表中，所以再将\{11,1\}加入到哈希表中。  
i=2时，9-7=2在哈希表中，此时迭代器也没有在末尾，所以执行 if 的语句，返回当前下标和哈希表中 target-nums\[i\] 的下标。

[38595e5e2f5e466ea2a00319e7cd7dd9.png]: https://img-blog.csdnimg.cn/38595e5e2f5e466ea2a00319e7cd7dd9.png
[31f0f38657224214bef335fdc6c81bd6.png]: https://img-blog.csdnimg.cn/31f0f38657224214bef335fdc6c81bd6.png