2Sum
最后更新于：2022-04-01 22:54:59
## 一、题目描述
基本意思是给定一组整数和一个常数target，试图在这一组数里找到两个数使得两者的和等于target，结果要求返回两个数的下标。
## 二、解题思路
思路一：使用暴力算法实现，这种情况下空间复杂度为O(1)，但是时间复杂度为O(n^2)，会超时。
思路二：使用hash表，存储每个数对应的下标，事件复杂度为O(n)。这样在查找某个值存不存在只需要常数时间。
~~~
//LeetCode, Two Sum
// 时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
vector twoSum(vector &num, int target) {
unordered_map mapping;
vector result;
for (int i = 0; i < num.size(); i++) {
mapping[num[i]] = i;
}
for (int i = 0; i < num.size(); i++) {
const int gap = target - num[i];
if (mapping.find(gap) != mapping.end() && mapping[gap] > i) {
result.push_back(i + 1);
result.push_back(mapping[gap] + 1);
break;
}
}
return result;
}
};
~~~
思路三：先排序（前提），然后利用头指针i和尾指针j找到两个数使得他们的和等于target。这种情况下，存在以下三种判断结果：
~~~
1.i+j = target，此时i和j就是能够满足条件的两个数，判断结束。
2.i+j > target, j不是满足条件的两个数，执行--j，继续判断；
3.i+j < target, i不是满足条件的两个数，执行++i，继续判断；
~~~
由于数组中可能存在相同的元素，并且满足条件的两个元素是相同的，因此，在找到第一个元素的坐标之后，需要更改第一个元素的值，为了方便起见，可以将第一个元素的值更改为第二个元素减去1，然后再寻找第二个元素的坐标。
该方法的核心代码：
~~~
//Two sum
int i = starting; //头指针
int j = num.size() - 1; //尾指针
while(i < j) {
int sum = num[i] + num[j];
if(sum == target) {
store num[i] and num[j] somewhere;
if(we need only one such pair of numbers)
break;
otherwise
do ++i, --j;
}
else if(sum < target)
++i;
else
--j;
}
~~~
这种方法存在以下边界条件，即当i>=j时，不存在两个元素的和等于给定的值，这种方法的时间复杂度O(n)，空间复杂度为O(1)。
上面的方法的前提是要对数组进行排序（排序的时间复杂度为O(nlogn)），然后使用上面的算法来寻找满足条件的两个元素，总的时间复杂度为O(nlogn)+O(n)=O(nlogn)，比起暴力算法的O(n^2)的时间复杂度大大改善。
## 三、解析
这道题属于面试里面一类经典的问题, 主要考察是否能够合理利用排序并设计出高效的算法。在设计算法时，需要考虑到数组事先并没有经过排序。另一个需要注意的地方是该题需要返回的是下标，而不是数字本身。
自己的代码需要进一步完善，后续更新。。。
参考链接：
[http://blog.csdn.net/sheng_ai/article/details/44211687](http://blog.csdn.net/sheng_ai/article/details/44211687)
[https://github.com/soulmachine/leetcode](https://github.com/soulmachine/leetcode)
';