给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
我的方法：
总的思路与3Sum()类似，也是用循环+双指针，只不过这里使用的是双重循环。同样的，在处理时应该注意以下两个方面：
- 注意剔除重复项。
- 当找到满足条件的项目时，不要忘了移动k,l，否则会进入死循环。
执行效率一般：执行用时 : 860 ms, 在4Sum的Python提交中击败了20.70% 的用户。内存消耗 : 10.7 MB, 在4Sum的Python提交中击败了14.94% 的用户。
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums.sort()
leng=len(nums)# 数组长度
ans=[]
if len(nums)<4:
return []
# 双重循环
for i in range(leng-3):
for j in range(i+1,leng-2):
k=j+1
l=leng-1
# k,l移动的条件
if i==0 or nums[i]!=nums[i-1]:
while k<l:
if nums[i]+nums[j]+nums[k]+nums[l]>target:
l-=1
elif nums[i]+nums[j]+nums[k]+nums[l]<target:
k+=1
else:
# 注意剔除重复项
if [nums[i],nums[j],nums[k],nums[l]] not in ans:
ans.append([nums[i],nums[j],nums[k],nums[l]])
# 不要忘了移动k,l
k+=1
l-=1
return ans
别人的方法：
这套方法看起来有点意思，基本思想是用递归把NSum转换为2Sum。还有其它有意思的点：
- 直接用results记录结果，子函数findNsum()中的return并不实际返回值，只是相当于break的功能。
- 依然是要先对nums排序，排序之后很多事情都好办多了，比如：判断什么情况下就不用再接着计算了。
- findNsum函数中的nums表示数组，target表示目标值，N表示相加的数字个数，result表示results[0]，results表示最终结果。
速度果然快了许多：执行用时 : 124 ms, 在4Sum的Python提交中击败了84.18% 的用户。内存消耗 : 10.7 MB, 在4Sum的Python提交中击败了14.94% 的用户。但递归应该不是速度更快的原因，应该是其中做了很多的跳过操作，节省了不少的时间。
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums.sort()
results = []
self.findNsum(nums, target, 4, [], results)
return results
def findNsum(self, nums, target, N, result, results):
if len(nums) < N or N < 2: return
# solve 2-sum
if N == 2:
l,r = 0,len(nums)-1
while l < r:
if nums[l] + nums[r] == target:
results.append(result + [nums[l], nums[r]])
l += 1
r -= 1
# 去重的方式很独特
while l < r and nums[l] == nums[l - 1]:
l += 1
while r > l and nums[r] == nums[r + 1]:
r -= 1
elif nums[l] + nums[r] < target:
l += 1
else:
r -= 1
else:
for i in range(0, len(nums)-N+1): # careful about range
if target < nums[i]*N or target > nums[-1]*N: # take advantages of sorted list
break
if i == 0 or i > 0 and nums[i-1] != nums[i]: # recursively reduce N
self.findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
return
