日期：20180910
题目描述：
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Examples：
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
详解：
这道题的难度是easy，没有多想直接遍历，下面是我的解。（C++）
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> sum;
int i,j;
for(int i=0;i<nums.size()-1;i++)
for(int j=i+1;j<nums.size();j++)
if(nums[i]+nums[j]==target){
sum.push_back(i);
sum.push_back(j);
return sum;
}
}
};
提交完结果168ms，击败了4.35%的C++提交者。我点开了第一名的答案，用时只有4ms。第一天刷leetcode就给我上了一课，原来人与人之间是有差距的。下面是4ms的代码。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
unordered_map<int, int> myMap; //使用无序映射，内部为哈希表实现
vector<int> res;
int size = nums.size();
for (int i = 0; i < size; i++) {
int val = target - nums[i];
if (myMap.find(val) != myMap.end()) { //找到了对应的值
res.push_back(myMap[val]);
res.push_back(i);
return res;
}
myMap[nums[i]] = i;
}
}
};
非常简洁的代码，速度非常快，简单来说之所以这么快是因为使用了无序映射。也就是代码中的unordered_map。无序映射的内部是由哈希表来实现的，所以在查找的时候速度非常的快，是常数的时间复杂度。而这道题目最核心的工作就是查找，无论哪一种方法都是遍历一遍数组，对于每一个遍历到的数，找到一个和它匹配的数就可以了。而我一开始自己做的方法，对于每一个数，找到和它匹配的数的方法就是再遍历一遍，这样的时间复杂度是O(n^2)。而用哈希表，查找的时间复杂度是常数，总共的时间复杂度是O(n)。
然后举个栗子来说明示例代码的过程：
例如输入是[1,2,3,6,7,10]和5，最终期待的输出是[1,2]。我们来看一下这个代码是怎么实现的。
遍历每一个元素，首先是i=0的时候，val = target - nums[0] = 4，if条件不成立，因为此时map中还什么都没有。这是跳过判断语句，执行myMap[nums[i]] = i;也就是给map中加入一个映射：1->0。意思就是说，值为1的数在下标为0的位置。
此时map中的键值关系情况：
1->0
然后开始遍历到第二个元素，也就是i = 1，nums[1] = 2，val = 3，目前map里只有一个键为1的元素，并没有键为3的元素，所以条件判断依然不会成立。然后执行myMap[nums[i]] = i，加入了一个2->1的键值对。
此时map中的键值关系情况：
1->0
2->1
然后遍历到第三个元素，也就是nums[2] = 3，val = 2，这是if条件判断语句终于能成立了，因为map里面有键为2的值。这时就匹配上了。返回的顺序是先返回res.push_back(myMap[val])，因为要先让下标小的数在前面，不然顺序反了输出结果就变成[2,1]了。
于是就大功告成了！
总结：
在C++中，map底层是用红黑树实现的，是有序的结构搜索，插入，删除都是O(logn)的时间复杂度。
unordered_map底层用哈希表实现，搜索是O(1)的时间复杂度。对于查找问题，可以考虑无序映射，即unordered_map。
网友评论