每日一题——两数之和

题目

给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）

数据范围：2≤len(numbers)≤10⁵ −10≤numbers_i 0≤target≤10⁹

要求：空间复杂度 O(n)，时间复杂度 O(nlogn)

示例1

输入：
[3,2,4],6
返回值：
[2,3]
说明：
因为 2+4=6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以返回[2,3]

示例2

输入：
[20,70,110,150],90
返回值：
[1,2]
说明：
20+70=90

思路

使用hashmap。遍历数组，如果没有 （target - 当前值） 就将当前数字存入hashmap，如果有，返回该数字下标即可。

解答代码

#include <unordered_map>
#include <vector>
class Solution {
public:/*** @param numbers int整型vector * @param target int整型 * @return int整型vector*/vector<int> twoSum(vector<int>& numbers, int target) {// write code herestd::vector<int> res;std::unordered_map<int, int> hash;for (int i = 0; i < numbers.size(); i++) {int tmp = target - numbers[i];auto it = hash.find(tmp);if (it != hash.end()) {// 在hash表中找到了res.push_back(it->second + 1);res.push_back(i + 1);break;} else {hash.emplace(numbers[i], i);}}return res;}
};