leedCode_1：两数之和

题目：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

思路：
方法一：
假设target由数组中的nums[i] 与未知数X构成，target = nums[i] +X,
如果X也在nums中，且index不等于i， 则找到了目标数据，返回i及X在nums中的index。

1. n = nums.size();
2. 第一层循环，遍历nums，认为nums[i] 为target的第一个加数；
3. 第二层循环，遍历nums中i～n-i ，是否存X，满足target-nums[i];
   时间复杂度为O(n*n)。

方法二：
基本思路与方法一是一样的，即默认num[i] 为构成target的加数之一，查找target-nums[i] 是否也存在于nums中。

1. 利用map的key-value 映射，
   map.insert(pair(num[i],index))；
2. 查找当key为targge-num[i]时，在map是否存在其value，即它在nums中的index。

代码：

//方法一
vector<int> TowSum(vector<int>& nums, int target)
{
    bool find = false, findOne = false;
    int other = 0, one = 0, oneIndex = 0;
    vector<int> out(2);
    for (unsigned i = 0; i < nums.size(); i++)
	{
		if (find)
			break;
		oneIndex = i;
		other = target - nums[i];
		for (unsigned k = i + 1; k < nums.size(); k++)
		{
			if (nums[k] == other)
			{
				find = true;
				out[0] = oneIndex;
				out[1] = k;
				break;
			}
		}
    }
    return out;
}

//方法二
vector<int> TowSum(vector<int>& nums, int target)
{
    vector<int> out(2,-1);
    map<int,unsigned> map;
    
    for (unsigned i = 0; i < nums.size(); i++)
    {
        map.insert(std::pair<int, unsigned>(nums[i], i));
    }
    
    for (unsigned i = 0; i < nums.size(); i++)
    {
        if (map.count(target - nums[i]) > 0 && map[target - nums[i]] != i)
        {
            out[0] = i;
            out[1] = map[target - nums[i]];
        }
    }
    return out;
}
//方法二改进
//在向map中写入映射数据对时，如果经判断，map中已经存在此数据，则认为找到target的第二个加数，返回结果即可
vector<int> TowSum(vector<int>& nums, int target)
{
    vector<int> out(2,-1);
    map<int,unsigned> map;
    for (unsigned i = 0; i < nums.size(); i++)
    {
        if (map.count(target - nums[i]) > 0 && map[target - nums[i]] != i)
        {
            out[0] = i;
            out[1] = map[target - nums[i]];
        }
        map.insert(std::pair<int, unsigned>(nums[i], i));
    }
    return out;
}