题解 | #两数之和#
两数之和
http://www.nowcoder.com/practice/20ef0972485e41019e39543e8e895b7f
双哈希表存储。
如果有重复的数字则使用第二个哈希表
代码如下
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)时间复杂度
