leetcode之2sum丶3sum(closest)丶4sum演算法總結

01-25

因為之前有在FCC上刷演算法題，覺得很有意思。最近在準備面試，所以跑到leetcode練習演算法。不料這裡的要求不是一般的高，尤其是時間複雜度。好了廢話少說，進入正題。

一丶Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

題目的意思：給定任意一個數組，和一個固定值，要求你在數組中找出滿足a+b = target的情況，並返回這兩個值的索引。當然數組裡的元素並非成線性排布。

這是leetcode上的第一題，我當時覺得非常簡單，而且和FCC有道題類似。先分析下思路，先固定數組裡的一個值，去收索另外一個值，代碼也很簡單。

var twoSum = function(numbers,target){ var len = numbers.length, res = []; for(var i = 0; i < len; ++i){ for(var j = i+1; j < len; ++j){ if(numbers[i] + numbers[j] === target){ res.push(i,j); } } } return res;}

這樣的代碼是能夠AC的，但是速度非常慢，最壞的情況就是索引值在最後兩位的情況。只打敗了9.10%的對手。（這裡只和JavaScript一門語言比較）。

如果想得到鍛煉和提升，肯定不能就此滿足，得想辦法優化。這裡題目有一點瑕疵，沒有考慮一個數組中有多組符合條件（a,b），所以後面的優化也只考慮解的唯一性。

下面思考一下，target這個值，如果存在滿足a+b = target，即target的值必定大於整個數組的最小值，那麼這樣就必定存在這樣的情況a,b中至少有一個數小於target/2,另外一個數必定大於target/2。那麼數組中就有可能存在一個值剛好等於target/2,或者最接近且不大於target/2。那樣我們在循環的時候就不用再從頭開始遍歷了。改進後的代碼如下：

這裡是按照題目的意思，返回索引先返回較小值。細心的朋友可能注意到這樣的一段代碼

temp = numbers.map(function(item){return item});

因為JavaScript中數組是引用類型，如果「淺複製」---直接var temp = numbers,後面我們所求的索引就會是排序之後的索引。所以我們這裡需要注意下。再次提交看看run time.--71.51%.比直接快了接近6倍。

再來我們繼續優化，看到上面的代碼確實速度提升了不少，但是代碼量也上去了啊，有沒有既滿足時間複雜度，又很簡潔的代碼呢？答案肯定是有的！接著上面的思路，想到了「夾逼定理」，這個定理還在在高中，解決壓軸題，我的數學老師給我講的，一晃這麼多年過去了。當時這個定理是為了解決一下很複雜的不等式證明。沒想到過今日它還能派上用場。我們設定兩個指針i丶j.一個指向數組頭部，一個指向尾部。sum = nums[i] + nums[j]。這樣我們只需要比較sum 與 target的情況，來移動指針，就可以快速求解。代碼如下：

因為two sum 整個題的唯一性，所以不用看考慮去重已經多個解的問題，這裡我重點在於建立思維.我們來看看它的運行速度，結果是75.8%。相比第二種方法，沒有多少提升。但是代碼卻是減少很多。

二丶3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:

[

[-1, 0, 1],

[-1, -1, 2]

]

這裡是直接將target的值設為0，而且我們看到，解不在是唯一性，所以要考慮去重。而且leetcode有嚴格的time控制，不能採用暴力窮舉的方式解題。題目中值給了一個例子，但是我在提交的過程中，發現還應該考慮到的一些特殊情況，比如[0,0,0,0],[0,0,0]...等等。

這裡我先說下思路：首先我們還是要做排序處理，然後我們固定最小的那個數，剩下的2個數採用和2sum一樣的解法，採用夾逼定理求解。但是不同點在於，這裡我要去重。因為返回的不在是索引值，而是具體的數值，所以不用考慮「深拷貝」，但是要留意temp[i] = temp[i-1](i!=0),的情況，就跳過下一次迭代。代碼如下：

那麼這個演算法究竟有多快呢？標題中的圖片已經告訴你答案beats 97.97%.可以說在JavaScript運算中已經極限了！下面我進入第三個問題。

三丶3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

這題有點亂入，從題目的意思就是最近 target的值。分析一下，何為最接近的值呢？a+b+c=target.就是最接近。那如果沒有這個情況我們要怎麼辦。這裡我們就需要把他轉換是成上面那個問題，也就是數學中的化歸思想。何為化歸？-----

我記得高中老師這樣給我舉例。給你一個空壺，一個水缸，一個燃氣台。教你燒一壺熱水。你會先把空壺裝滿水，放上去，打開火。然後燒開。接著給你第二個問題。已經有一個壺冷水，叫你燒開。我該怎麼做，化歸思想就是，先把水倒乾淨，就得到了一個空壺，我們就回到了第一個問題

那麼這裡其實也是一個思路，上面的target是固定值0，這裡target是任意值，怎麼辦呢？不如令sum = a + b + c, 用diff = Math.abs(sum - target),和0 做比較。不就回到了3sum的問題了嗎？所以代碼如下：

這裡說下運算速度，只打敗了40.28%的對手，感覺很意外,我以為會達到60%左右，所以應該有其他辦法來優化。這裡我暫時還沒有想到。

好了，看到這裡，你是否有自己的理解了？數學中的有一個重要的方法--「數學歸納法」，既然我們能求2sum,3sum.那麼4sum,5sum,nSum...我們有沒有辦法了？

四丶4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:

[

[-1, 0, 0, 1],

[-2, -1, 1, 2],

[-2, 0, 0, 2]

]

第一次我提交的代碼嚴重超時了，因為忽略一個問題，遞歸其實很費時間，循環次數太多。只是代碼很整潔。所以還是把這個不是很好的演算法講講，當一個錯誤的案例。分析下思路：先創一個用於遞歸的help函數，幫我們添加符合條件的子數組到ret里。還會涉及一個臨時數組path用於存儲目標元素，temp用於複製path,核心代碼就是每一次都push一個元素到path里，同時用一個變數表示4個元素的和。以及下一次的索引值，再次帶入這個helper函數。所以他需要6個參數，helper（nums, index, path, cursum, target, res）。代碼如下：

代碼看起來還是不多，思路也比較容易想，可是AC的時候報超時了。所以需要新的演算法來解決這個問題

這裡我只提一種解法，也就最後通過了測試的演算法。繼續延用2sum,3sum的思路，還是先做排序處理，然後固定2個兩個數，求出他們的和，用sum = target-a-b來表示剩餘2個元素的c,d要滿足"target "，即tmp = c + d,這裡用tmp和sum來比較差異，再次利用夾逼定理找到滿足的子數組mid,然後創建用於複製的數組ret,。如果只是做了這些工作還遠遠不夠，因為4sum為0的情況要比3sum複雜的多，譬如給定數組[-3,-1,0,0,1,3]那麼他的正確結果就是[-3,0,0,3]丶[-3,-1,1,3]丶[-1,0,0,1]。而[-3,-1,0,0,0,1,3]的結果和上面是一樣的，所以我們避免這樣的情況發生。由於我求解mid數組肯定是按非遞減排布的，這裡JavaScript應該是沒有直接比較兩個數組是否相等的辦法，而用indexOf也是異常麻煩，既然順序是一致的那麼-1001必定是和-1001想等的，所以我們利用字元串來檢查是否存在這樣的一個組合，如果不存在，才能push到最後的result中，否則跳過這次循環。代碼如下：

至此leetcode關於Nsum的問題就結束了，覺得寫的還可以的朋友點個贊吧，另外也虛心請教有沒有更好演算法？後續會繼續更新有關演算法的問題，另外FCC中級，高級演算法解析在成都梁朝偉 - 博客園