题目描述

传送门-力扣

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

同类型题目

三数之和

思路

与三数之和不同，这里返回的是下标，因此不能直接用排序+双指针的方法，如果想用这种方法可以定义新的结构和运算符重载。这里采用另一种方法。

  1. 因为是两数之和，a + b = target，遍历数组取一个数为 a ，那么只需要直到 target - a 是否也在当前数组中即可。
  2. 考虑到数组查找问题，可以用哈希来减小时间复杂度，通过一次循环，每次取a，然后判断 target - a 是否在哈希表中。
  3. 如果找到 target - a ，则将找到的值的坐标、当前值的坐标加入到结果中，没找到则不处理。
  4. 不管找没找到，都将<当前值，当前索引>加入到哈希表中，继续下一次。

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> mymap;
        vector<int> res;
        for(int i = 0; i < nums.size(); i++)
        {
            if(mymap.find(target - nums[i]) != mymap.end())
            {
                res.push_back(mymap.find(target - nums[i])->second);
                res.push_back(i);
            }
            mymap.insert(make_pair(nums[i], i));
        }
        return res;
    }
};