said in 4Sum O(N^2) solution python code:

class Solution(object):

### my own code, run time is O(N*N)

def fourSum(self, nums, target):

"""

:type nums: List[int]

:type target: int

:rtype: List[List[int]]

"""

#nums.sort()

length = len(nums)

d = dict()

for i in xrange(length):

for j in xrange(i+1, length):

val = nums[i] + nums[j]

if val in d:

d[val].append((i,j))

else:

d[val] = [(i,j)]

res = set()

for k in d:

val = target - k

if val in d:

vlist = d[val]

klist = d[k]

for (i,j) in vlist:

for (l,m) in klist:

ilist = [i,j,l,m]

if len(set(ilist)) != len(ilist):

continue

mylist = [nums[i], nums[j], nums[l], nums[m]]

mylist.sort()

res.add( tuple(mylist) )

return list(res)

Clever but the running time doesn't decrease obviously. And the method is not general, just for 4 sum questions.

However, it's enlightened