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
