最簡單的算法題，你會嗎？

問題： 給定一個數組例如[1,3,4,6,7] ，再給定一個目標數，例如9。 寫一個算法找出兩個數他們相加等於目標數，返回他們在數組中的位置。給出一個解即可，同一個數字不能使用2次。

比如[1,3,4,6,7] 目標數為9，那麼需要返回[1,3]。如果目標數為20，返回null。

首先問題需要明確的幾點：

• 給定的數組是否是有序的？

• 數組中的數字是否會重複？

如果這是在面試中被問到的體面，你必須向面試官確認。這個有利於給你加分的哦。

題目中沒有明確說明是有序數組，一般認為是無序的，也沒說明同一數字不能重複出現，所以也必須考慮數字會重複的情況。也就是說要考慮[1,2,2,3,4,4,5]這種情況

笨辦法：for嵌套循環兩次，這個辦法是最容易想到的辦法。但是算法時間複雜度在O（n^2),效率不行。這裡不多介紹。

我們來看看好辦法：

先把問題轉化下， x + y = target 那麼可以變成 x = target - y 。那麼只需要循環一遍，每次循環查看 target-y 是否存在在數組中。 那麼算法時間複雜度至少是O(n） 因為至少要遍歷一遍。至於到底是多少，就要看target-y 存在在數組的判斷有多快了。判斷某個值是否存在，我們往往用到的數據結構是hash set 或者 hash map 。他們查詢速度都是O(1) 所以算法總體速度還是O(n)

確定了大致解題思路，那我們來細看下還會碰到什麼問題。

這個hash set 或者 hash map 要怎麼構建。這個根據自己所熟悉的語言，來使用語言現成的數據類型就好了。比如python 可以使用字典，javascript 直接使用數組（javascript 數組即可以當數組用也可以當字典用）就好。

那麼字典裡保存什麼樣的內容呢？

• 首先容易想到的是把給出的數組按照值為key,索引為value的方式。

• 比如[1,3,4,6,7] 我們可以創建一個字典為｛1：0，3：1，4：2，6：3，7：4｝

• 這種方式會有一個問題，比如我們的數組是[1,2] 給定目標數是4。這樣我們的字典就是｛1:0,2:1}。 但是由於同一個數字不能使用2次，所以這裡還要多做一步判斷操作，判斷我們取的兩個數的索引相不相同。如果不同就說明找到了。假如如果我們給定數組中存在相同值，問題又變複雜了，比如[1,2,2,3,3] 給定目標數是5，這時候字典要怎麼存呢？ ｛1：[0],2:[1,2],3:[3,4]}可以看到如果考慮存在相同值的情況，我們字典的值需要保存一個數組。這又加大了判斷的複雜度。

這裡的技巧是我們以target-x 為key，x的索引為value的方式保存。邊創建字典邊判斷。

每次循環先判斷當前這個數是否存在在字典中，如果存在就表示，這個數是前面某個數的target-x數。而我們字典中保存了這個數的索引，所以如果找到只要返回前面某個數的索引，以及當前數的索引。一次遍歷搞定。同時，也因為是先判斷是否存在在字典中，如果不存在再添加到字典中，所以解決了查找結果是自己的問題。

附上代碼：

• var twoSum = function(nums, target) {

• if(nums.length <= 0 ){

• return null;

• }

• var dic = [];

• for(var i=0; i< nums.length; i++){

• if( dic.hasOwnProperty(nums[i])){

• return [dic[nums[i]],i];

• }else{

• dic[target-nums[i]] = i;

• }

• }

• return null

• };