题目
给出一个整型数组 numbers 和一个目标值 target,请在数组中找出两个加起来等于目标值的数的下标,返回的下标按升序排列。
(注:返回的数组下标从1开始算起,保证target一定可以由数组里面2个数字相加得到)
数据范围:2≤len(numbers)≤105 −10≤numbersi≤109 0≤target≤109
要求:空间复杂度 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,如果有,返回该数字下标即可。
![](https://img.haomeiwen.com/i2199186/1e41ec0dca36c103.gif)
解答代码
#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 here
std::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;
}
};
网友评论