C++ unordered_map哈希表

@toc

基本用法

//初始化
unordered_map<int, int> umap = { {2, 10},{1, 20},{3,30} };

//遍历unordered_map
//注意一个用指针一个用点
for (auto &item : umap) {
	cout << item.first << " -> " << item.second << endl;
}
for(auto it = umap.begin();it != umap.end();++it)  {
	cout<<it->first<<" "<<it->second<<endl;
}     

//插入元素
//一般插入
umap.insert(pair<int,int>(4,9));  
//数组的形式，如果存在就修改，否则插入
umap[3] = 7;           
umap[5]=99; 

//按key删除元素
umap.erase(0);
//按迭代器删除元素
umap.erase(umap.begin());

//按key查找元素
auto it = umap.find(3);
if(it != umap.end()){   //查找成功，修改其值
	it->second=50;
}
else{    //查找失败，直接插入
	umap[3]=88;
}

一道例题

leetcode: 49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

思路：
开一个哈希表unordered_map<string,vector<string>> umap;
遍历strs，如果排好序的strs[i]在umap的键中，则将未排好序的strs[i]，添加到该键对应的vector数组中；如果不在umap的键中，则加入即可。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;   //保存最后结果
        unordered_map<string,vector<string>> umap; 
        for(int i=0;i<strs.size();i++){
            string temp=strs[i];
            sort(temp.begin(),temp.end());
            auto it = umap.find(temp);
            if(it != umap.end()) 
                it->second.push_back(strs[i]);
            else{
                vector<string> temp1;
                temp1.push_back(strs[i]);
                umap[temp]=temp1;
            }
        }
        for (auto &item : umap) {
            res.push_back(item.second);
        }
        return res;
    }
};

又一道例题（两数之和）

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> umap;
        for(int i=0;i<nums.size();i++){
            if(umap.find(target-nums[i])!=umap.end()){
                return {umap.find(target-nums[i])->second,i};
            }
            else{
                umap.insert({nums[i],i});
            }
        }
        return {0,0};  //这个返回没有任何意义
    }
};