2Sum

最后更新于:2022-04-01 22:54:59

## 一、题目描述 ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-01-05_568bb5e7e0b0b.jpg) 基本意思是给定一组整数和一个常数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)
';