需求
给定一个包含 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]]
方法一：排序 + 双指针
本题和(15)题的思路一致，排序后，2层遍历，通过双指针进行范围选取，并判断是否符合要求；
为提升效率，有几个优化细节
排序后可以对4个元素和的极值与target比较，排除掉一些情况；
第一层遍历，取到倒数第4位即可，类似的排除一些极值情况；
第二层遍历，取到倒数第3位即可，类似的排除一些极值情况；
第三层循环前，可以排除掉一些重复元素；参考代码
def four_sum(nums, target):
nums.sort()
res = []
if len(nums) < 4 or not nums: return res
if nums[-4] + nums[-3] + nums[-2] + nums[-1] < target: return res
if nums[0] + nums[1] + nums[2] + nums[3] > target: return res
for f in range(len(nums) - 3):
if nums[f] + nums[-3] + nums[-2] + nums[-1] < target:
continue
for t in range(f + 1, len(nums) - 2):
if nums[f] + nums[t] + nums[-2] + nums[-1] < target:
continue
l = t + 1
r = len(nums) - 1
if (f > 0 and nums[f] == nums[f - 1]) or (t > (f + 1) and nums[t] == nums[t - 1]):
continue
while l < r:
four_ele = [nums[f], nums[t], nums[l], nums[r]]
if sum(four_ele) == target:
res.append(four_ele)
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]: l += 1
while l < r and nums[r] == nums[r + 1]: r -= 1
elif sum(four_ele) < target:
l += 1
else:
r -= 1
return res
nums = [1, 0, -1, 0, -2, 2]
target = 0
print(four_sum(nums, target))
[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
方法二：排列组合
使用
itertools模块的combinations()方法，对数组进行组合，通过推导式筛选出和为target的组合；要求答案不能重复，筛选出的组合，通过排序
sorted()和集合set()进行去重复操作；该方法效果不高，序列元素个数少时，非常方便。
参考代码
from itertools import combinations
def four_sum(nums, target):
result = set(tuple(sorted(i)) for i in list(combinations(nums, 4)) if sum(i) == target)
return list(result)
nums = [1, 0, -1, 0, -2, 2]
target = 0
print(four_sum(nums, target))
[(-1, 0, 0, 1), (-2, 0, 0, 2), (-2, -1, 1, 2)]
