基于3-sum 但是时间不行了：
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums.sort()
if len(nums) < 4:
return []
if len(nums) == 4:
if nums[0] + nums[1] + nums[2] + nums[3] == target:
return [[nums[0],nums[1],nums[2],nums[3]]]
else:
return []
i = 0
res = []
while i < len(nums) - 3:
j = i + 1
while j < len(nums) - 2:
m = j + 1
n = len(nums) - 1
while m < n:
if nums[i] + nums[j] + nums[m] + nums[n] < target:
m += 1
elif nums[i] + nums[j] + nums[m] + nums[n] > target:
n -= 1
else:
res.append([nums[i],nums[j],nums[m],nums[n]])
m += 1
n -= 1
while m < n and m != j + 1 and nums[m] == nums[m-1]:
m += 1
while m < n and n != len(nums) - 1 and nums[n] == nums[n+1]:
n -= 1
while j < len(nums) - 2 and nums[j] == nums[j+1]:
j += 1
j += 1
while i < len(nums) - 3 and nums[i] == nums[i+1]:
i += 1
i += 1
return res
第二种解法ac:
两两数字之和存到字典中，value为下标组成的远足
两重循环扫描list，target - 和存在字典中，如果字典中元祖下标大于j，那么添加数组的值
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
res = []
dic = {}
for p in range(len(nums) - 1):
for q in range(p+1,len(nums)):
if nums[p] + nums[q] not in dic:
dic[nums[p] + nums[q]] = [(p,q)]
else:
dic[nums[p] + nums[q]].append((p,q))
for i in range(len(nums) - 3):
for j in range(i+1,len(nums) - 2):
t = target - nums[i] - nums[j]
if t in dic:
for k in dic[t]:
if k[0] > j:
temp = [nums[i],nums[j],nums[k[0]],nums[k[1]]]
temp.sort()
if temp not in res:
res.append(temp)
return res
