力扣刷题-哈希表

  哈希表就是在关键字和存储位置之间建立对应关系。也就是：

  在C++中可以使用无序容器来实现：

//头文件
#include<unordered_map>
//定义，这里表示key和value都是int型。
unordered_map<int, int> map = {{1, 1}, {2, 2}, {3, 4}};
//迭代器
map.begin();
map.end();

  下面举例：
  给定一个整数数组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]
    那么在这里，对于一个固定值target，我要找到数组中的对应元素以及他们的下标，那就先建立起数组元素key和他们下标value的映射，这样就构建出了一个哈希表map，map用来存放遍历过的元素，比如示例1，当开始遍历元素2时，我想找到7是否遍历过，因为9-2=7，但是发现没有，因此更新哈希表，将key=2和value=0放进map表中，然后开始遍历7，在map中找有没有元素2，如果找到了，返回map中{2， 0}集合，取value=0和value=1，即构成了示例1的答案。

vector<int> twoSum(vector<int>& nums, int target)
{
    unordered_map<int, int> idx;//构建<key, value>容器集合
    for(int i = 0; i < num.size(); i++)
    {
        auto it = idx.find(target - nums[i]);//查找有没有target - nums[i]
        if(it != idx.end())//如果找到了
        {
            return {it->second, i};//it->second是在取value
        }
        idx[nums[i]] = i;//更新哈希表
    }
    return {};
}

  使用哈希表的时间复杂度为$\small{O(N)}$，空间复杂度为$\small{O(N)}$。比暴力解法$\small{O(N^2)}$要快。