## 一、題目描述  基本意思是給定一組整數和一個常數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)