"""
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

 

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：

输入：nums = []
输出：[]
示例 3：

输入：nums = [0]
输出：[]
 

提示：

0 <= nums.length <= 3000
-105 <= nums[i] <= 105
通过次数411,176提交次数1,337,782

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""

from typing import *

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        record = []
        if len(nums) < 3:
            return record
        for i in range(len(nums)-2):
            left = 0 - nums[i]
            start, end = i+1, len(nums) - 1
            while start < end:
                s = nums[start] + nums[end]
                if s == left:
                    toAdd = (nums[i], nums[start], nums[end])
                    if toAdd not in record:
                        record.append(toAdd)
                    start, end = start + 1, end - 1
                elif s < left:
                    start += 1
                else:
                    end -= 1
        return record