Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b+ c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.
Example:
Given array nums = [, , -, , -, ], and target = . A solution set is:
[
[-, , , ],
[-, -, , ],
[-, , , ]
]
思路
在看到这道题之后，我第一反应是使用之前求三数之和那样求四数之和，结果也是可行，但是运行结果显示的时间复杂度太高。这里我先将我自己的解决思路写下来
时间复杂为O(n3),空间复杂为O(1)。
解决代码
class Solution:
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
if len(nums) < : # 异常情况，小于四个直接返回
return []
if len(nums) == and sum(nums) == target:
return [nums]
nums.sort() # 先进行排序
res = []
for i in range(len(nums)-): # 第一个下标
if i > and nums[i] == nums[i-]: # 遇到重复的直接跳过
continue
for j in range(i+, len(nums)-): # 第二个下标
if j > i+ and nums[j] == nums[j-]: # 遇到重复直接跳过
continue
start, end = j+, len(nums)-1 # 另外两个下标，指向头和尾部
while start < end:
tem = nums[i] + nums[j] + nums[start] + nums[end]
if tem - target > : # 进行判断，选择相应的移位
end -=
elif tem - target < :
start +=
else: # 找到符合条件的四个数字。
res.append([nums[i], nums[j], nums[start], nums[end]]) # 将其添加进结果集中
while start < end and nums[start] == nums[start+]: # 相同元素直接跳过。
start +=
while start < end and nums[end] == nums[end-]: # 相同元素直接跳过
end -=
start +=
end -=
return res
改进
上面的算法，在实现之后效率太低，以至于运行结果之超过了百分之10的用户。但是由于自己也想不出什么好的办法，因此取讨论区看了别人的写法，不得不说确实很厉害。下面写上别人给出了一个解决方法，这个方法可以解决N数和的问题。
解决思路以及代码
这个问题他的解决思路主要是通过分解，将N数和的问题转化为两数和的问题（递归），并且通过传递变量来记录满足结果的条件。
def fourSum(self, nums, target):
nums.sort()
results = []
self.findNsum(nums, target, , [], results) #因为本题是4数之和的问题，所以传入的参数是4，并且将保存满足条件的数字的变量进行传递
return results def findNsum(self, nums, target, N, result, results):
if len(nums) < N or N < : return # 数组的长度小于N（N数之和）时或者小于2时，直接返回条件。
# solve -sum
if N == : # 当N == 2 时，进行判断， 里面的步骤和三数问题中的步骤一样。
l,r = ,len(nums)-
while l < r:
if nums[l] + nums[r] == target:
results.append(result + [nums[l], nums[r]])
l +=
r -=
while l < r and nums[l] == nums[l - ]:
l +=
while r > l and nums[r] == nums[r + ]:
r -=
elif nums[l] + nums[r] < target:
l +=
else:
r -=
else: # N大于2时进行递归，分解
for i in range(, len(nums)-N+): # careful about range # 第一个指针位置
if target < nums[i]*N or target > nums[-]*N: # 意外情况判定，因为数组是已经排好序的，当第一个元素(最小)乘
break # 以N时，还比target大，那说明，后面的都不满足，直接返回。后面同理。
if i == or i > and nums[i-] != nums[i]: #recursively reduce N #从第一个看是遍历，并将相应额结果进行传递。
self.findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
return