Two-Sum问题描述
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
想法与实现
指针法
一开始，最先想到的做法是向算法课上解决3-SUM的方法那样，首先排序，然后维护两个指针，一个是初始化指向第一个元素，一个初始化指向最后一个元素，当指针指向的两个元素的和小于target的时候，就右移第一个指针，如果和大于target，那就左移第二个指针；思路大概就是这样。
因为看题目似乎默认没有重复元素（其实有一组用例是[0, 4, 3, 0], 0，说明是有相同元素的，但是这个用例中很巧正好应该选择两个相同的元素，因此还是AC了，如果用例变成[0, 0, 4, 3], 3，我的输出就是[1, 2]，就错了，只能说运气好= =），因此为了确定原本的次序，首先备份了原本的数据，然后在找到对应排序后的数据的两个元素后，再遍历一遍原本的数据，找到原本的次序。代码如下~
vector<int> twoSum(vector<int> &numbers, int target) {
// save the data
vector<int> buf = numbers;
// the pointer define
int i = 0;
int j = numbers.size() - 1;
sort(numbers.begin(),numbers.end());
int sumTmp = numbers[i] + numbers[j];
while (sumTmp != target)
{
if (sumTmp > target)
{
j--;
}
else if (sumTmp < target)
{
i++;
}
else
{
break;
}
sumTmp = numbers[i] + numbers[j];
}
vector<int> answer;
int length = buf.size();
for (int k = 0; k < length; k++)
{
if (buf[k] == numbers[i] || buf[k] == numbers[j])
answer.push_back(k + 1);
}
return answer;
}
前面基本没有变化，只是多了后面的遍历，时间复杂度还是排序的复杂度，但是这样做的话，空间复杂度变为了O(n)，要有栈上的空间存储原本的数据。
哈希表
看题目的提示，用哈希表来做可以实现O(n)的时间复杂度，O(n)的空间复杂度，于是就尝试想了想。方法其实很简单，就是维护一个key为数组元素，value为数组下标的哈希表，对于numbers[i]和target，寻找key为target - numbers[i]的元素，如果找到，就OK了。代码实现如下~
vector<int> twoSumHash(vector<int> &numbers, int target) {
vector<int> answer;
map<int, int> hashTable;
int length = numbers.size();
for (int i = length - 1; i >= 0; i--)
{
hashTable.insert(make_pair(numbers[i], i));
}
for (int i = 0; i < length; i++)
{
map<int, int>::iterator buf = hashTable.find(target - numbers[i]);
if (buf != hashTable.end() && i != buf->second)
{
answer.push_back(i + 1);
answer.push_back(buf->second + 1);
}
}
return answer;
}
其中有问题的地方在于重复元素的处理。还是测试用例：[0,4,3,0], 0，在这里用了一个很tricky的方式绕过了这个用例，就是在建立哈希表的时候倒序建立，这样哈希表中key为0对应的value为3，在循环体里面处理的时候，就可以得到正确的结果，但是这样的做法肯定不是正确的，比如测试用例：[0, 0, 4, 0], 0，正确的输出为[1, 2]，此种做法的输出仍为[1, 4]。
总结
总而言之，如果要考虑重复变量的话，可能前面的做法修改起来要简单一点，而如果要哈希表支持重复变量，可能就不那么简单了。