# 4Sum O(N^2) solution python code

• use a dictionary to store all the 2Sum results. and then use this dictionary to get all 4Sum results. the time complexity is O(N*N).

``````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()
return list(res)
``````

• Any one know how to post code in easy reading format?
@house3618 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[val].append((i,j))
else:
d[val] = [(i,j)]
res = set()
for k in
val = target - k
if val in
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()
return list(res)
}

• Btw this is not the right place to post solution.

• 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()