基础 （map,pair的使用详解）/题目 两数之和 讲解 哈希表的使用

力扣题目链接(opens new window)https://leetcode.cn/problems/two-sum/

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

讲之前 先来说一下用到的知识 并且讲一下知识点

——————————————————pair———————————————————————

    pair 只含有两个元素，可以看作是只含有两个元素的结构体，不想写结构体时可以偷懒用这个代替一下

    应用 1，代替二元结构体   2，作为map键值对进行插入代码如下

map<string,int>mp;
//插入
mp.insert(pair<string,int>("ding ge sen",1));
//or  mp.insert(make_pair<string,int>("ding ge sen",1));
//or  mp.insert({"ding ge sen",1});

#include<utility>
//头文件

//初始化
pair<string,int>p("ding ge sen",1);//带初始值的
pair<string,int>p;//不带初始值的

//赋值
p=make_pair("ding ge sen",19);
p=pair<string,int>("ding ge sen",19);
p={"ding ge sen",19};

访问 

pair<string,int>p[20];//定义结构体数组
for(int i=0;i<20;i++){
 cout<<p[i].first<<p[i].seccond<<endl;//first，seccond是别名哈
}
//我们还可以这样访问
vector<pair<string,int>>p(20);//这样子就是动态了
for(int i=0;i<p.size();i++){
cout<<p[i].first<<p[i].seccond<<endl;
}

pair大致就这样了下面我们讲map

————————————————————map—————————————————————

映射类似与函数，一个x对应一个y值，在map这是一个键对应一个值

容器中一个存储对为一个键值对，包含两个元素（键和值）

基本特性

• 有序：std::map 是基于红黑树实现的，因此存储的元素是有序的，按照键的顺序排列。（键的类型必须可以排序）
• 唯一键：每个键在 std::map 中是唯一的，不能重复。
• 插入与查找时间复杂度：插入和查找操作的平均时间复杂度为 O(log n)。

1，初始化

//初始化定义
map<string, string> mp;
map<int, int> mp;
map<int, node> mp;//node是结构体类型
.......

2,插入

std::map<std::string,int>jue;
//平时会直接加using namespace std;所以后面还有前面我就不加std::
//插入元素
jue["ding ge sen"]=19;
jue["zxb"]=19;
//另一种插入
jue.insert(make_pair("ldy",19));

3,查找

auto it = jue.find("key");  //fide（）放键值
if (it != jue.end()) {  
    std::cout << "key's age: " << it->second << std::endl;  
} else {  
    std::cout << "key not found." << std::endl;  
}//返回键为key的映射的迭代器 注意：用find函数来定位数据出现位置，它返回一个迭代器。当数据存在时，返回数据所在位置的迭代器，数据不存在时，返回jue.end() 

mp.count(key)//查看元素是否存在，因为map中键是唯一的，所以存在返回1，不存在返回0 o(logn)

4，遍历访问

//迭代器访问
map<int,int>mp;
map<int,int>mp::iterator it;
for(it=mp.begin;it!=mp.end();it++){
cout<<it->first<<' '<<it->second<<endl;//it是指针所以用->
}
//智能指针访问
for(auto i : mp)
cout << i.first << " " << i.second << endl;//键，值
//还可以下标访问
mp[dgs]=19;

5，逆向遍历

mp.rbegin()  返回指向map最后一个元素的迭代器（地址）O(1)

mp.rend()     返回指向map第一个元素前面(上一个）的逆向迭代器（地址） O(1)

map<int,int> mp;
mp[1] = 2;
mp[2] = 3;
mp[3] = 4;
auto it = mp.rbegin();
for(auto it=mp.rbegin;it!=mp.rend();it++){
	cout << it->first << " " << it->second << endl;
}

answer
3 4
2 3
1 2

6,二分查找

mp.lower_bound()   返回一个迭代器，指向键值>= key的第一个元素

mp.upper_bound()  返回一个迭代器，指向键值> key的第一个元素

解释一下什么意思呢，就是括号里面是你们想查找的键的大小，然后由于map容器是可以按照键值自动排序（从小到大），要记得的是查找的是键而不是值

#include <iostream>  
#include <map>  

int main() {  
    // 创建一个 map，键为 int，值为 string  
    std::map<int, std::string> mp;  
    mp[1] = "one";  
    mp[3] = "three";  
    mp[5] = "five";  
    mp[7] = "seven";  

    int key1 = 4;  
    int key2 = 5;  

    // 使用 lower_bound 查找  
    auto it1 = mp.lower_bound(key1);  
    if (it1 != mp.end()) {  
        std::cout << it1->first << " " << it1->second << std::endl;  
    } else {  
        std::cout << "lower_bound(" << key1 << ") not found, exceeds all elements." << std::endl;  
    }  

    // 使用 upper_bound 查找  
    auto it2 = mp.upper_bound(key2);  
    if (it2 != mp.end()) {  
        std::cout  << it2->first << "  " << it2->second << std::endl;  
      }
    }  

    return 0;  
}

     代码解析

1. 创建了一个 std::map<int, std::string>，其中键是整数，值是字符串。
2. 插入了一些键值对：1->"one"，3->"three"，5->"five"，7->"seven"。
3. 使用 lower_bound 查找键值为 4 的元素：
   • 因为没有 4，lower_bound(4) 会返回第一个键大于或等于 4 的元素，即 5，输出 5 five。
4. 使用 upper_bound 查找键值为 5 的元素：
   • 因为存在 5，upper_bound(5) 会返回第一个键大于 5 的元素，即 7，输出 7  seven。

还有一个就是unordered_map

map：内部用红黑树实现，具有自动排序（按键从小到大）功能。

unordered_map：内部用哈希表实现，内部元素无序杂乱

unordered_map这玩意等之后再写一篇单独讲

最后我们就来解一下开头的题

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int>map;//用来储存nums中元素并且因为map中键是唯一的，所以可以把nums[i]当作键值存入
        for(int i=0;i<nums.size();i++){
            auto iter=map.find(target-nums[i]);
            //利用auto自动识别iter相应的类型
            if(iter!=map.end()){
                return {iter->second,i};
            }
            map.insert(pair<int,int>(nums[i],i));
        }
       return {};
    }
};

整体题的原理就是

往map里面存nums的值，利用map键值是唯一，让nums元素的值放在键的位置，索引放在值的位置，然后auto iter=map.find(target-nums[i]);这一步就是判断map里面有没有能满足的，有的话就直接把那个键对应的值和i返回，如果都不满足，就最后返回{}；

返回值带{}是因为返回值类型是vector<int>