[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)写法。

一：

二：