两数之和

描述

给定一个整数数组 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]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

unordered_map

初始化

unordered_map<string, int> map1; map1[string("abc")] = 1; map1["def"] = 2;//创建空map，再赋值
unordered_map<string, int> map2(map1);    //拷贝构造
unordered_map<string, int> map3(map1.find("abc"), map1.end());    //迭代器构造
unordered_map<string, int> map4(move(map2));    //移动构造
unordered_map<string, int> map5 {{"this", 100},{"can", 100},};//使用initializer_list初始化

常用操作

map1.at("abc");	//查找具有指定key的元素，返回value
map1.find("abc");    //查找键为key的元素，找到返回迭代器，失败返回end()
map1.count("abc");    //返回指定key出现的次数，0或1
map1.emplace(make_pair("str1", 1));    //使用pair的转换移动构造函数，返回pair<unordered_map<string, int>::iterator, bool>
map1.emplace("str2", 2);    //使用pair的模板构造函数，如果key已经存在则什么都不做
map1.insert(pair<string ,int>("sex", 1));//插入元素，返回pair<unordered_map<string, int>::iterator, bool>
map1.insert(unordered_map<string, int>::value_type("sex", 1));//插入元素，如果key已经存在则什么都不做
map1.insert(make_pair("sex", 1));//插入元素，返回pair<map<string, int>::iterator, bool>，插入成功second为true，失败为flase
map1.insert({"sex", 1});    //使用initializer_list插入元素
map1.insert(map1.end(), {"sex", 1});//指定插入位置，如果位置正确会减少插入时间
map1.insert(map2.begin(), map2.end());//使用范围迭代器插入
map1.erase("abc");	    //删除操作，成功返回1，失败返回0
map1.erase(map1.find("abc"));	    //删除操作，成功返回下一个pair的迭代器
map1.erase(map1.begin(), map1.end());    //删除map1的所有元素，返回指向end的迭代器
map1.empty();        //是否为空
map1.size();        //大小
map1.bucket_count();    //返回容器中的桶数
map1.bucket_size(1);    //返回1号桶中的元素数
map1.bucket("abc");    //abc这个key在哪一个桶
map1.load_factor();    //负载因子，返回每个桶元素的平均数，即size/float(bucket_count);
map1.max_load_factor();//返回最大负载因子
map1.max_load_factor(2);//设置最大负载因子为2，rehash(0)表示强制rehash
map1.rehash(20);//设置桶的数量为20，并且重新rehash
map1.reserve(20);//将容器中的桶数设置为最适合元素个数，如果20大于当前的bucket_count乘max_load_factor，则增加容器的bucket_count并强制重新哈希。如果20小于该值，则该功能可能无效。
unordered_map<string, int>::iterator it = map1.begin();	    //返回指向map1首元素的迭代器
unordered_map<string, int>::const_iterator c_it = map1.cbegin();	    //返回指向map1首元素的常量迭代器
unordered_map<string, int>::local_iterator it = map1.begin(1);//返回1号桶中的首元素迭代器
unordered_map<string, int>::const_local_iterator c_it = map1.cbegin(1);//返回1号桶中的首元素的常量迭代器
pair<unordered_map<string, int>::iterator, unordered_map<string, int>::iterator> it = map1.equal_range("abc");//返回一个pair，pair里面第一个变量是lower_bound返回的迭代器，第二个迭代器是upper_bound返回的迭代器
map1.clear();        //清空

我们不仅要知道元素有没有遍历过，还有知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。

再来看一下使用数组和set来做哈希法的局限。

• 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
• set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。

此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value在保存数值所在的下标。

C++中map，有三种类型：

映射	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::map	红黑树	key有序	key不可重复	key不可修改	O(log n)	O(log n)
std::multimap	红黑树	key有序	key可重复	key不可修改	O(log n)	O(log n)
std::unordered_map	哈希表	key无序	key不可重复	key不可修改	O(1)	O(1)

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。这道题目中并不需要key有序，选择std::unordered_map 效率更高！

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;
        for(int i=0; i<nums.size(); i++){
            //遍历当前元素，并在map中寻找是否有匹配的key
            auto iter = map.find(target-nums[i]);
            if(iter != map.end())
                return {iter->second, i};//返回两个下标
            // 如果没找到匹配对，就把访问过的元素和下标加入到map中
            map.insert(pair<int, int>(nums[i], i));
        }
        return {};
    }
};