map小试牛刀，LeetCode界的abandon有多难？
map小试牛刀，LeetCode界的abandon有多难？
作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
今天我们来看关于map用法的一道例题，也是LeetCode必刷问题之一。它就是LeetCode第一题——两数之和。
这道题堪称是LeetCode界的abandon，不知道多少人弃坑就是从这题开始的……
两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
分析
首先，这题给定的范围刚好
的复杂度不会被卡，所以我们直接暴力可以通过。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
vector<int> ret;
for (int i = 0; i < n; i ++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] + nums[j] == target) {
ret.push_back(i);
ret.push_back(j);
return ret;
}
}
}
return ret;
}
};
如果熟悉map应用的话，可以很容易想到我们可以凭借map来查找元素是否存在。这样的话我们就可以不用通过遍历去查找了，可以将查找的性能优化到
。
我们使用map记录下每个元素出现的下标，这样我们只需要一重循环枚举当前元素m，然后通过判断target - m是否存在在map当中即可知道是否存在答案。
但是如果直接上手提交的话，会发现有trick。比如[3, 2, 4], target = 6。由于数组中出现了3，3在map当中，当我们判断6- 3 = 3时，会发现同样也在map当中。所处我们要针对这种情况进行特判，判断target - m的下标必须和m不同。即它们为不同的元素。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
vector<int> ret;
map<int, int> mp;
for (int i = 0; i < n; i++) {
mp[nums[i]] = i;
}
for (int i = 0; i < n; i++) {
int num2 = target - nums[i];
// 特判num2和num1下标不同
if (mp.count(num2) && mp[num2] != i) {
ret.push_back(i);
ret.push_back(mp[num2]);
break;
}
}
return ret;
}
};
利用map，我们只需要两次遍历就可以找到答案，整体复杂度是
，完美搞定，这也是复杂度最优的方法了。
如果是在面试当中，写出这样的代码基本上就OK了。但本着尽善尽美的原则， 其实这题还有优化的空间，或者说有更优雅的写法。
我们遍历了两次数组，一次是将元素插入到map当中，另外一次是寻找答案。我们能不能把这两个步骤进行合并，只遍历一次数组？在插入元素的同时寻找答案？这样我们就可以减少掉一次对数组的遍历。
这当然是可行的，不过需要我们对逻辑进行调整。还是要考虑到出现两个相同元素构成答案的情况。因为map当中的键值对是唯一的，如果出现两个相同的key，会导致后者覆盖前者。所以我们要先判断答案存不存在，再插入map。
其实只需要对上面的代码稍作改动即可，代码如下：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
vector<int> ret;
map<int, int> mp;
for (int i = 0; i < n; i++) {
int num2 = target - nums[i];
if (mp.count(num2)) {
ret.push_back(mp[num2]);
ret.push_back(i);
return ret;
}
mp[nums[i]] = i;
}
return ret;
}
};
到这里其实还没有结束，还可以继续优化。比如说可以使用set来替代map，甚至由于题目中每个元素的范围不大，我们还可以直接使用长度1e4的数组来标记元素是否出现过，这样可以进一步把复杂度降低到
。
这道题虽然难度不大，但是非常适合初学者从最简单的暴力解法一点点向最优的解法推导。这种一点点优化的过程还是很有成就感也是收获非常大的。