两数之和–利用哈希表（查询）空间换时间

写博客，只为熟悉和梳理下常见算法知识点~训练脑子hhh

题目描述：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
思路：看到这道题我直接的思路就是暴力解法，外面一个循环遍历nums[i],里面一个循环，找数组中是否存在target-nums[i],这样的复杂度就是O(n2).查看了别人的评论代码，发现通过哈希表进行查询，可以简化时间到O(n),代码如下（leetcode仅提交Solution类）：

#include<bits/stdc++.h>
using namespace std;
class Solution{
public:
vector<int> twoSolution(vector<int> &nums,int target)
{
unordered_map<int,int> map;
for(int i=0;i<nums.size();i++)
{
if(map.find(target-nums[i])!=map.end())
return{map[target-nums[i]],i};
map[nums[i]]=i;
}
return {};
}
};
int main()
{
vector<int> example={2, 7, 11, 15};
int target=9;
Solution wisdom=Solution();
vector<int> output=wisdom.twoSolution(example,target);
cout<<output[0]<<" "<<output[1]<<endl;
}

为了更清除理解哈希表的作用，下面想对程序中的unordered_map与map做一个小小的比较：

map VS unordered_map

C++中有2类键值对型容器-map与unordered_map,二者在不同场景下作用不同。

map

map基于红黑树实现，保障了良好情况下最坏的时间，可以在O(logn)时间完成查找。

• 对单次时间敏感的场景，比如生活实际操作（不容许一次失误的那种），建议使用map。
• 红黑树是一种二叉查找树，二叉查找树一个重要的性质是有序。对于一些需要用到有序性的应用场景，建议使用map。

unordered_map

基于hash_table实现，它的最大优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。

二者提交的结果比较：

	map
	unordered_map

最后

以上就是怡然小虾米为你收集整理的两数之和--利用哈希表（查询）空间换时间C++两数之和–利用哈希表（查询）空间换时间的全部内容，希望文章能够帮你解决两数之和--利用哈希表（查询）空间换时间C++两数之和–利用哈希表（查询）空间换时间所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。