题15：类型：双指针、数组
- 题目：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
- 本题采用双指针方法，给定主指针i并且遍历完成排序的数组（本题由小到大排序），前后指针来寻找nums[i] + nums[start] + nums[tail] = 0，双指针的范围为[i + 1, len(nums) - 1]之间，故i范围为[0,len(nums)-2]；
需要注意的是，数组中有重复数值需要跳过，所以i，start，tail三者都需考虑重复情况。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort() # 先从小到大排序
res = []
for i in range(len(nums) - 2):
start = i + 1
tail = len(nums) - 1
if i>0 and nums[i] == nums[i-1]: # 相同数值跳过，即只计算一次
continue
while start < tail: #确保前后指针顺序不颠倒
target = nums[i] + nums[start] + nums[tail]
# 满足条件时，添加数组到结果数组中
if target == 0:
res.append([nums[i],nums[start],nums[tail]])
# i不变，前后指针可能存在其它数值满足条件，例如0，-4,4和0-5,5
start += 1
tail -= 1
#同理，start和tail也只计算相同的数一次
while start < tail and nums[start] == nums[start-1]:
start += 1
while start < tail and nums[tail] == nums[tail+1]:
tail -= 1
elif target > 0:
tail -= 1
else:
start += 1
return res
- 小知识：sort()函数与sorted()区别及相关知识。
题18：类型：双指针、数组
- 题目：给定一个包含 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]
]
方法一：排序+双指针
- 本题思路与三数和类似，只不过外面需要再套一个j循环，同时也需要避免重复。
- 值得一提的是，本题避免i重复处，为 i-1>j 而不是 i>j 有如下解释，若i>j情况，即j，i相邻情况下，nums[i-1]是实际上属于j的范围，跨循环会发生错误。虽然避免了重复，但其实是j和i的重复，不是i内部。
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
res = []
nums.sort()
for j in range(len(nums)-3):
if j > 0 and nums[j] == nums[j-1]:
continue
#减少特殊情况的时间开销
if nums[j]+nums[j+1]+nums[j+2]+nums[j+3] > target:
break # j 固定情况下，因为数组从小到大排列，最小三数和 大于则失败
if nums[j]+nums[len(nums)-1]+nums[len(nums)-2]+nums[len(nums)-3] < target:
continue#若 最大三数和 小于，j循环继续
for i in range(j+1,len(nums)-2):
if i-1>j and nums[i] == nums[i-1]: # 相同数值跳过，即只计算一次
continue
start = i + 1
tail = len(nums) - 1
while start < tail: #确保前后指针顺序不颠倒
sum_four = nums[i] + nums[start] + nums[tail]+nums[j]
# 满足条件时，添加数组到结果数组中
if sum_four == target:
res.append([nums[j],nums[i],nums[start],nums[tail]])
# i不变，前后指针可能存在其它数值满足条件，例如0，-4,4和0-5,5
start += 1
tail -= 1
#同理，start和tail也只计算相同的数一次
while start < tail and nums[start] == nums[start-1]:
start += 1
while start < tail and nums[tail] == nums[tail+1]:
tail -= 1
elif sum_four > target:
tail -= 1
else:
start += 1
return res
网上的方法二：排列组合
- 使用
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)]
