leetcode 001 两数之和(附加unorder_map的使用)

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

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

unorder_map介绍:

这题首先可以想到用两个for循环解决,复杂度$$O(n^2)$$,当然,这个方法太笨了,不是我们想要的,我们可以通过一边哈希表的遍历就可以得出结果。我们可以使用C++的STL中的unorder_map来实现哈希表。unorder_map和map的区别就在于,前者是无序的(这里所谓的无序,是真正的完全无序,与插入顺序也没有关系),而后者的底层通过红黑树来实现,是有序的,所以在此题中,使用前者要比使用后者速度快。下面介绍几个unorder_map的常规用法:

插入数据:

unorder_map要求键是唯一的,当我们需要插入数据的时候,可以使用如下代码:

1
2
unorder_map<int,int> mp;
mp[target]=i;

通过值来寻找键名:

1
2
3
it=mp.find(value);
printf(it->first);//打印键
printf(it->second);//打印值

解题思路:

此题需要注意的一点是,‘你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。’这句话。比如输入nums[3,3],target为6,返回的应该是0,1而不是0,0.我们在遍历nums时同时建立哈希表,用target减去我们当前遍历到的数值,如果得到的值存在于哈希表中,就证明我们找到了那两个下标。如果不存在,我们就把当前遍历到的值映射到哈希表中,这样一来也能避免刚刚提到的“0,0”问题。这样一来,我们就将复杂度降低到了$$O(n)$$.

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class 
{
public:
vector<int> twoSum(vector<int> &nums, int target)
{
map<int, int> mp;
vector<int> ans;
for (int i = 0; i < nums.size(); i++)
{
int k = target - nums[i];
if (mp.find(k) != mp.end())
{
ans.push_back(i);
ans.push_back(mp[k]);
}
else
mp[nums[i]] = i;
}
return ans;
}
};

提交结果:

成绩还不错,时间复杂度击败了93.5%的用户