描述
给一个包含n个数的整数数组S，在S中找到所有使得和为给定整数target的四元组(a, b, c, d)。
样例
例如，对于给定的整数数组S=[1, 0, -1, 0, -2, 2] 和 target=0. 满足要求的四元组集合为：
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)
注意事项
四元组(a, b, c, d)中，需要满足a <= b <= c <= d
答案中不可以包含重复的四元组。
V1: 利用三数之和的思想再加一层循环，这种方法的时间复杂度是O(n3)，会超出时间限制。
class Solution:
def fourSum(self, numbers, target):
p = []
numbers.sort()
for i in range(len(numbers)-3):
t1 = target - numbers[i]
for j in range(i+1, len(numbers)-2):
t2 = t1 - numbers[j]
q = {}
for k in range(j+1, len(numbers)):
t3 = t2 - numbers[k]
if numbers[k] in q:
a = numbers[i]
b = numbers[j]
c = t3
d = numbers[k]
l = (a,b,c,d)
if l not in p:
p.append(l)
else:
q[t3] = k
return p
V2: 将四个数字分成两部分，将第一部分两个数字之和和它们的下标存入字典，用target减去剩下两个数字之和设为t2，在字典中寻找t2，找到后对比它们的下标，排序后返回结果。这种方法的时间复杂度是O(n2)，空间复杂度也是O(n2)，但提交的时候也会超过时间限制。
class Solution:
def fourSum(self, numbers, target):
p = []
q = {}
numbers.sort()
for i in range(len(numbers)):
for j in range(i+1, len(numbers)):
t1 = numbers[i]+numbers[j]
if t1 not in q: #这条语句其他博客里有用q.keys()，.keys()返回的是一个list，判断一个元素是否在list里是O(n)的，而判断元素是否在dict里是O(1)的
q[t1] = [(i,j)]
else:
q[t1].append((i,j))
for m in range(len(numbers)):
for n in range(m+1, len(numbers)-2):
t2 = target - numbers[m] - numbers[n]
if t2 in q:
for index in q[t2]:
if index[0] > n: #此处为了排列顺序，但是四个数的组合会重复两次，所以要去重
l = (numbers[m],numbers[n],numbers[index[0]],numbers[index[1]])
if l not in p: #如果p声明的是set()则不用判断，因为集合会去重
p.append(l)
return p
V3: 我想这几道题的意思不止是解决单个的题目，而是可以推广到解决N数之和，在这里借鉴了前辈的代码加以学习。采用了递归的思想，先判断N是否等于2，如果比N大那么用递归先固定N-2个数，再判断两数之和。
class Solution:
def fourSum(self, numbers, target):
numbers.sort()
results = []
self.NSum(numbers, target, 4, [], results)
return results
def NSum(self, numbers, target, N , result, results):
if len(numbers) < N or N < 2:return
if N == 2:
l = 0
r = len(numbers)-1
while l < r:
if numbers[l] + numbers[r] == target:
results.append(result +[numbers[l],numbers[r]])
l+=1
r-=1
while numbers[l] == numbers[l-1]:
l+=1
while numbers[r] == numbers[r+1]:
r-=1
elif numbers[l] + numbers[r] < target:
l+=1
else:
r-=1
else:
for i in range(0,len(numbers)-N+1):
if numbers[i]*N > target or numbers[-1]*N < target:
break
if i == 0 or i > 0 and numbers[i-1] != numbers[i]:
self.NSum(numbers[i+1:], target-numbers[i], N-1, result+[numbers[i]],results) #在这里递归
return results
网友评论