## 一、题目描述  基本意思是给定一组整数和一个常数target，试图在这一组数里找到两个数使得两者的和等于target，结果要求返回两个数的下标。 ## 二、解题思路 思路一：使用暴力算法实现，这种情况下空间复杂度为O(1)，但是时间复杂度为O(n^2)，会超时。 思路二：使用hash表，存储每个数对应的下标，事件复杂度为O(n)。这样在查找某个值存不存在只需要常数时间。 ~~~ //LeetCode, Two Sum // 时间复杂度O(n)，空间复杂度O(n) class Solution { public: vector<int> twoSum(vector<int> &num, int target) { unordered_map<int, int> mapping; vector<int> 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)