leetcode 1 Two Sum(在无序数组中找两个数之和与目标值相等，两种方法)

    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.
Example:
    Given nums = [2, 7, 11, 15], target = 9,
    Because nums[0] + nums[1] = 2 + 7 = 9,
    return [0, 1].
    题目的大概意思是：在无序的数组中找两个数，使得这两个数之和与给定的目标值相等。返回这两个数的下标。
    解法一：遍历数组中的每一个数，判断当前数字与它之后的数字之和是否与目标值相等。时间复杂度为o(n*n)，空间复杂度为o(1)。

vector<int> twoSum(vector<int>& nums, int target) 
{
	vector<int> res(2,-1);
	if(nums.size() < 2)
		return res;
	for(int i = 0; i < nums.size() - 1; ++i)
	{
		for(int j = i + 1; j < nums.size(); ++j)
		{
			if(nums[i] + nums[j] == target)
			{
				res[0] = i;
				res[1] = j;
				return res;
			}
		}
	}
	return res;
}

解法二：使用hash表存储遍历过的元素，遍历数组中的每一个元素，当遍历该元素时，去hash表中进行查找，是否存在某个元素与当前元素之和与目标值相等。时间复杂为o(n)，因为我们只需要遍历一遍数组即可，但是空间复杂度为o(n)。典型的以空间换取时间。

vector<int> twoSum(vector<int>& nums, int target)
{
	vector<int> res(2, -1);
	if (nums.size() < 2)
		return res;
	unordered_map<int, int> hash;
	for (int i = 0; i < nums.size(); ++i)
	{
		int leftNum = target - nums[i];
		if (hash.find(leftNum) != hash.end())
		{
			res[0] = hash.find(leftNum)->second;
			res[1] = i;
			break;
		}
		hash[nums[i]] = i;
	}
	return res;
}