[leetcode]4Sum @ Python

原題位址：http://oj.leetcode.com/problems/4sum/

題意：從數組中找到4個數，使它們的和為target。要求去重，可能有多組解，需要都找出來。

解題思路：一開始想要像3sum那樣去解題，時間複雜度為o(n^3)，可無論怎麼寫都是time limited

exceeded。而同樣的算法使用c++是可以通過的。說明python的執行速度比c++慢很多。還說明了一點，大概出題人的意思不是要讓我們去像3sum那樣去解題，否則這道題就出的沒有意義了。這裡參考了kitt的解法：http://chaoren.is-programmer.com/posts/45308.html

　　　　  

需要用到哈希表的思路，這樣可以空間換時間，以增加空間複雜度的代價來降低時間複雜度。首先建立一個字典dict，字典的key值為數組中每兩個元素的和，每個key對應的value為這兩個元素的下标組成的元組，元組不一定是唯一的。如對于num=[1,2,3,2]來說，dict={3:[(0,1),(0,3)],

4:[(0,2),(1,3)],

5:[(1,2),(2,3)]}。這樣就可以檢查target-key這個值在不在dict的key值中，如果target-key在dict中并且下标符合要求，那麼就找到了這樣的一組解。由于需要去重，這裡選用set()類型的資料結構，即無序無重複元素集。最後将每個找出來的解(set()類型)轉換成list類型輸出即可。

代碼：

再貼兩個過不了的o(n^3)寫法。

一：

二：