LeetCode刷题之旅（1）--两数之和（简单题）

算法，永远是检验一个程序员的能力大小的重要指标，也是提升自身能力所必备的专业技能。所以现在就要动手练习，同时，可以对C++有更加深刻的认识和理解。而LeetCode上可以和各位算法爱好者一起学习，是一个很好的平台。好好加油吧<->

题目:两数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路：

方法一：

使用两个for循环，从头到尾遍历nums，同时对比即可，这个方法很简单，但是时间复杂度为$O(n^2)$,实际的执行时间也到了180ms左右，显然不太好（代码在下面的注释里）。

方法二：

使用以空间换时间的方法，那也就是哈希表了，这里的思路就是使用关联容器中的无序集合类型——unordered_map。
在C++11中关联容器支持高效的关键字查找和访问。在此题中，使用map的思路就是，首先看是否能够find到target-nums[i]的值，如果能找到，就说明在nums中存在两个数字满足题意，那么直接返回两者的对应下标即可，也就是i，和r[key]；如果找不到target-nums[i]，那么就初始化map的键值对，这里可能乍一看怎么没有初始化map，其实不然，每一次没有找到就会初始化一个值，这样效率最高。例如：实例中的例子，一开始的key=9-2=7,map此时为空，所以找不到，那么初始化r[2]=0,然后再循环key=9-7=2，刚好有2，然后就可以返回下标i=1,r[2]=0，完毕。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int>r;
        int i=0;
        for(i=0;i<nums.size();i++)
        {
            int key=target-nums[i];
            if(r.find(key)!=r.end())
            {
                return vector<int>({i,r[key]});
            }
            r[nums[i]] = i;
        }
    }
    /*
    vector<int> result;
	for (int i = 0; i < nums.size(); i++)
	{
		for (int j = i + 1; j < nums.size(); j++)
		{
			if (nums[i] + nums[j] == target)
			{
				result.push_back(i);
				result.push_back(j);
				return result;
			}
		}
	}*/
};

执行用时：8 ms