梦开始的地方-力扣001 两数之和

力扣001题-两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

暴力解法

看到题目第一眼想到的是嵌套循环，很简单，代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

        for(int i = 0; i<nums.size(); i++){
            for(int j = 0; j<nums.size(); j++){
                if(nums[i]+nums[j] == target && i!=j){
                    return {i,j};
                }
            }
        }
        return {};
    }
};

显然双循环写法时间复杂度为O(n^2),下面我们来看一种时间复杂度为O(n)的解法。

哈希表法

这种解法我们利用C++中unordered_map这种数据结构的哈希表底层实现，以O(n)时间复杂度来解出这题。
首先，我们要知道什么是哈希表。
哈希表是根据关键码的值而直接进行访问的数据结构。
这种说法可能难以理解，简单地说，数组其实也是一种哈希表。数组的下标就是它的关键码，通过下标的值可以直接访问其数据。
常见的哈希结构有三种：数组、unordered_set、unordered_map。本题使用unordered_map,那么为什么选择这种结构呢？
数组：大小固定，当元素很少而哈希值很大时将会造成内存浪费
unordered_set:是一个集合，只能存放key值，而本题既要判断某值是否存在还要记录它的下标
unordered_map:key value存储结构，本题中用key保存数值，用value保存其下标

思路

遍历数组，判断map中是否存在与当前遍历元素相加等于target的元素。有，则返回下标；无，则将当前遍历元素存入map。
代码如下：

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

总结

什么时候应该想到使用哈希表？
当我们需要查询一个元素是否出现过或是否存在于某个集合，我们就应该想到使用哈希表。
本题中，我们需要一个集合来存放遍历过的元素，在遍历过程中我们又需要判断某元素是否是否遍历过，即判断某元素是否存在于集合。