Two-sum
本文最后更新于 2167 天前（2017-6-15），其中的信息可能已经有所发展或者不再适用于现阶段。
本文全长 399 字，全部读完大约需要 2 分钟。
题目描述
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2
题目分析
这道题目主要考查了 hash 的知识，在 C++ 的 STL 中的对应实现是 map。哈希表可以在常数时间内找到一个 key 对应的 value。
算法一开始首先将 numbers 的每一个值作为 key，相应的下标作为 value，全部存入 map 中。然后，从 numbers 的第一个数开始搜索，具体的说，对于每个 number，令 diff = target – numbers[i]，我们需要知道 diff 是否存在于 numbers 中，这时利用之前已经初始化好的 map，即可在 O(1) 时间内得到结果。若存在且下标比i大，则找到了答案，将其保存并退出循环。算法整体复杂度为 O(n)
参考代码
class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
map<int, int> m;
vector<int> ans;
int diff = 0;
for (int i = 0; i < numbers.size(); ++i) {
m[numbers[i]] = i;
}
for (int i = 0; i < numbers.size(); ++i) {
diff = target - numbers[i];
if (m.find(diff) != m.end() && i < m[diff]) {
ans.push_back(i + 1);
ans.push_back(m[diff] + 1);
break;
}
}
return ans;
}
};