LeetCode 两数之和

• 2021 年 8 月 7 日
• 筆記
• 算法系列

1.两数之和

LeetCode传送门

题解

#include <vector>
#include <map>
class Solution {
public:
    std::vector<int>
        twoSum(std::vector<int> & nums, int target)
        {
            std::vector<int> result;
            std::map<int,int> map;
            for(int i=0;i<nums.size();i++)
            {
                if(map.count(target - nums[i]) > 0)
                {
                    result.push_back(map[target - nums[i]]);
                    result.push_back(i);
                    return result;
                }
                map[nums[i]] = i;
            }
            return result;
        }
};

解题思路：

• 首先需要创建一个map哈希表
• 然后利用map的count函数去匹配哈希表中存储的所有的key，如果匹配不到对应的key就存储一下
• 如果匹配到了key，就说明已经成功找出了两个相加等于target的数字了

举例

数组：nums = [8,2,7,9,10]
参数：target=9
输出：[1,2]

当for里的i=0的时候，此时执行9-8=1，但是我们的map还是个空哈希表，count肯定不会生效，就会把nums[i]放map里，而map数据如下

当for里的i=1的时候，此时会执行9-2=7，很明显nums下是有7的，但是我们是通过map的key去查找的，很显然，count依然不会生效，所以还是会进行存储操作,此时map数据如下

当for里的i=2的时候，此时会执行9-7=2，执行到这里的时候，可以看到map内是有2这个key的。所以此时count会i命中判断。
然后我们取出2对应的V=1，在拿到当前循环的i，就可以正确的得到两个索引值，然后输出即可