题解 | #两数之和#

双哈希表存储。
如果有重复的数字则使用第二个哈希表

代码如下

class Solution {
public:
/**
*
* @param numbers int整型vector
* @param target int整型
* @return int整型vector
*/
vector<int> twoSum(vector<int>& numbers, int target) {
// write code here
unordered_map<int, int> m1,m2;
int len=numbers.size();
for(int i=0;i<len;++i)
{
if(!m1.count(numbers[i])) m1[numbers[i]]=i+1;
else m2[numbers[i]]=i+1;
}
for(auto &p:m1)
{
int i=p.first;
if(target-i!=i&&m1.count(target-i))
{
if(p.second<m1[target-i]) return{p.second,m1[target-i]};
else return{m1[target-i],p.second};
}
if(m2.count(target-i))
{
if(p.second<m2[target-i]) return{p.second,m2[target-i]};
else return{m2[target-i],p.second};
}
}
return {};</int></int>

}

};

O(N)时间复杂度