2.1　兩數之和

我們先拿最基礎的加法運算來入門。兩數之和是一道很簡單的題目，作為力扣（LeetCode）上的第一個問題，相信它是大多數人刷題的起點。

題目描述（第1題）

給定一個整數數組nums和一個目標值target，請你在該數組中找出和為目標值的那兩個整數，并返回它們的索引值。你可以假設每種輸入只會對應一個答案，但是，你不能重復利用這個數組中同樣的元素。

示例

給定 nums=[2,7,11,15]，target=9

因為 nums[0]+nums[1]=2+7=9，所以返回[0,1]

解法一　排序+雙指針（不符合題意）

思路

首先想到的最簡單粗暴的方法是，使用兩層循環找出所有的兩兩組合，逐個判斷其和是否等于target，如果相等則直接返回。暴力解法的時間復雜度是O(n2)，空間復雜度是O(1)，平方階意味著算法效率不高，不妨嘗試一下別的方法。

可以先對數組進行一次排序，不妨采用升序，這樣就可以使用雙指針中的頭/尾指針法來解決這個問題了。以題目中的[2,7,11,15]為例，由于數組本身就是有序的，經過一次升序排序不會發生變化。之后建立頭/尾指針，分別指向2和15，將兩者相加即2+15=17，得到17。

17大于目標值9，由于數組是升序的，因此需要將尾指針向前移動，這樣加起來的值才可能變小。經過一次移動之后，頭/尾指針分別指向2和11，此時2+11=13。

13還是大于目標值9，因此尾指針繼續前移，現在頭/尾指針分別指向2和7。

將其相加，2+7=9，發現正是要找的數，于是返回其對應的索引值[0,1]。

總結一下，在進行一次升序排序后，分別取首/尾元素，即最小值和最大值，如果相加大于 target，那么較大的數和其他所有的數相加的結果就沒有必要看了，肯定都不滿足，向前移動一下尾指針將其剔除。按照這樣的邏輯繼續執行，直到找到滿足條件的數的組合。

代碼

復雜度分析

●　時間復雜度：算法瓶頸在于排序，因此時間復雜度為O(nlogn)，其中n為數組長度。

●　空間復雜度：不確定，取決于內部排序算法的具體實現。

上面的解法是有缺陷的，因為排序會導致原數組的索引發生變化，在本題要求下這種方法是不可取的（如果仍然想用排序法解決，可以將索引值作為第二維信息保存）。不過發散思維、多做嘗試是正確的，對之后做題會有幫助，將來碰到類似的問題時也能夠很快提取到這些信息。另外，這種算法的時間復雜度是O(nlogn)，時間復雜度并不是很好，那么是否可以在線性時間內解決這個問題呢？

解法二　空間換時間

思路

我們可以通過一個輔助的哈希表來降低時間復雜度，具體思路是：對數組進行遍歷，遍歷每一項時都判斷target-nums[i]（其中i是當前數組項的索引值）是否在之前遍歷中遇到過，如果是，則直接返回；如果不是，則將其放在哈希表中，然后繼續遍歷下一項。

代碼

復雜度分析

●　時間復雜度：O(n)，其中n為數組長度。

●　空間復雜度：O(n)，其中n為數組長度。

這種方法能夠在線性時間內完成，但是相應地使用了額外的n的空間。這在很多情況下是值得的，不但可以使程序運行得更快，代碼也更簡潔，這種算法對于這種需要返回索引的場景非常有效。比如題目要求返回的兩個索引值按照在原數組中出現的先后順序返回；又或者題目要求按照元素值的大小返回，我們也只需要拿出來比較一下，返回即可。總的來說，這種算法能應用的場景更多，代碼更簡潔，在沒有對空間復雜度有特殊要求的場景下是首選。