# –*– coding:utf-8 –*–
# @Time : 2023/2/8 22:08
# @Author : taotao
# @File : 15.py
# @Software : PyCharm
# 题目描述 难度：中等
“””
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
“””
# 算法描述
“””
三支针移动法：
首先对于数组进行升序排序，然后按照下述方法进行查找即可
（1）定义三个指针k,i,j。其中 k 指向三个数字中最小的一个数字，i在（k, len(nums)）向左移动， j在（k, len(nums)）向右移动。如果满足 0 = nums[k] + nums[i] + nums[j]
则成功找到一组。
（2） 完成一次判断后再次移动由于要排除重复的元素，则不管上一次是否匹配成功，需要判断nums[i]和nums[i-1]或者nums[j]和nums[j+1]是否相等，如果相等，则直接跳过，排除掉重复的元素
（3） k + 1, 循环匹配完成所有元素
“””
# 快排算法，也可以直接调用python的api函数
def quick_sort(nums):
return nums
def handle(nums):
“””
:param
nums: 目标数组
:return
: 三元组和为0的集合
“””
# 首先对于数组进行排序
nums = sorted(nums)
res = []
for k in range(0, len(nums) – 2): # k从0到数组倒数第三个元素
if nums[k] > 0: break # 如果nums[k] > 0 直接打破循环，后面不可能等于0
if nums[k-1] == nums[k]: continue # 如果nums[k] = nums[k-1] 排除重复的情况，直接结束本次循环。
i = k + 1
j = len(nums) – 1
while i < j:
# 满足要求的情况
if nums[i] + nums[j] + nums[k] == 0:
res.append((nums[k], nums[i], nums[j]))
j -= 1
i += 1
# 跳过重复的元素
while nums[j] == nums[j+1] and i < j: j -= 1
while nums[i] == nums[i-1] and i < j: i += 1
elif nums[i] + nums[j] + nums[k] < 0:
i += 1
# 跳过重复的元素
while nums[i] == nums[i-1] and i < j: i += 1
elif nums[i] + nums[j] + nums[k] > 0:
j -= 1
# 跳过重复的元素
while nums[j] == nums[j+1] and i < j: j -= 1
return res
if __name__ == “__main__”:
nums = [-1, 0, 1, 2, -1, -4]
res = handle(nums)
print(res)