Description
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.
Example
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
Discussion
看到这个问题的第一眼，最容易想到的方法自然是暴力破解。外层循环遍历每一个数，内层循环搜索符合条件的另一个数。暴力破解的复杂度为O(n^2)。
外层循环难以优化，必然要遍历每一个数。内层的搜索如果可以转变为常数时间，那么整个算法的效率将会非常高。Java中我们可以采用Hash_Map来将搜索的时间复杂度变为O(1)。C++中我们可以采用unordered_map来将搜索的时间复杂度变为O(1)。这样，算法整体复杂度就降低到了O(n)。
unordered_map属于C++11的新特性，是一个关联容器，包含带有唯一键的键值对。搜索，插入和去除具有常数时间复杂度。
算法的时间复杂度为O(n)。
C++ Code
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> answer;
unordered_map<int, int> map;
for (int i = 0; i < nums.size(); ++i)
{
map[nums[i]] = i;
}
for (int i = 0; i < nums.size(); ++i)
{
answer.push_back(i);
int numToFind = target - nums[i];
if (map.find(numToFind) != map.end() && map[numToFind] != i)
{
answer.push_back(map[numToFind]);
return answer;
}
answer.clear();
}
return answer;
}
};