leetcode_1 两数之和

https://leetcode-cn.com/problems/two-sum/

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

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

思路：

比较容易想到的解法是双重循环。

std::vector<int> twoSum(std::vector<int>& nums, int target)
{
   size_t size = nums.size();
   if( size == 0)
       return std::vector<int>{0};
   std::vector<int> res;
   for(size_t i = 0;i < size;i++)
   {
       int other = target - nums[i];
       for(size_t j = i+1; j < size;j++)
       {
           if(nums[j] == other)
           {
               res.emplace_back(i);
               res.emplace_back(j);
               break;//找到一组解就退出
           }
       }
   }
   return res;
}

另一种解法可以使用map。
key = 数组元素，value = 下标。可以从双重循环变为一次遍历，降低时间复杂度为O(n);
遍历数组元素nums[index]时，检查map[target - nums[index]] 是否存在。不存在就将该元素插入map中，map[nums[index]] = index;存在的话就找到一组解，返回{index，map[target - nums[index]]} 即可。

std::vector<int> twosum(std::vector<int>& nums, int target)
{
    std::vector<int> vec;
    std::map<int, int> tmpMap;
    for (size_t i = 0; i < nums.size(); i++)
    {
        int other = target - nums[i];
        if (tmpMap.find(other) != tmpMap.end())
        {
            vec.emplace_back(tmpMap[other]);
            vec.emplace_back(i);
            break;
        }
        else
        {
            tmpMap[nums[i]] = i;
        }
    }
    return vec;
}

tips:
size_t 是一个无符号长整型。

for(size_t i = 10;i >= 0;i--)
{
    ......//可能会导致core dump
}