思路分析
这类nSum问题有一种基本思路，就是首先对序列排序，然后使用指向头尾的指针i、j进行遍历。如果num[i] + num[j] > val，则说明两者之和应该减小，即j--，否则应有i++。在相等时，则可以退出循环。这一方法的复杂度为O(n*logn)，主要由排序所引起。这一方法可以推广到n更大时的情形。
对于2Sum问题，相比之下，存在一种复杂度大概同样为O(n*logn)的更好想的做法，即使用set存储所有数字。然后单向遍历一遍，如果剩余值存在于set中，则遍历一下找到剩余值即可。这里如果将set改为unordered_set，即哈希表，则能够将平均复杂度降低到O(n)，属于典型的空间换时间。
代码
此处贴上使用set的算法。
class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
set<int> S;
vector<int> res;
for ( int i = 0; i < numbers.size(); i++ ) S.insert(numbers[i]);
for ( int i = 0; i < numbers.size(); i++ ) {
if ( S.find(target - numbers[i]) != S.end() ) {
for ( int j = i + 1; j < numbers.size(); j++ ) {
if ( numbers[i] + numbers[j] == target ) {
res.push_back(i + 1);
res.push_back(j + 1);
return res;
}
}
}
}
}
};
以及使用头尾指针（需要先排序）的算法：
:::C++
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int> result;
int i = 0, j = numbers.size() - 1;
while (i < j) {
int sum = numbers[i] + numbers[j];
if (sum > target) {
j--;
} else if (sum < target) {
i++;
} else {
result.push_back(i + 1);
result.push_back(j + 1);
break;
}
}
return result;
}
};