给你一个包含 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
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/3sum
如果我们直接使用三重循环枚举三元组，会得到 O(N^3)个满足题目要求的三元组（其中 N 是数组的长度）时间复杂度至少为 O(N^3)。在这之后，我们还需要使用哈希表进行去重操作，得到不包含重复三元组的最终答案，又消耗了大量的空间。这个做法的时间复杂度和空间复杂度都很高，因此我们要换一种思路来考虑这个问题。
我们保持三重循环的大框架不变，只需要保证：
第二重循环枚举到的元素不小于当前第一重循环枚举到的元素；
第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。
如果我们固定了前两重循环枚举到的元素 a 和 b，那么只有唯一的 c 满足 a+b+c=0a+b+c=0。当第二重循环往后枚举一个元素 b′时，由于 b' > b，那么满足 a+b'+c'=0 的 c′一定有 c' < c，即 c ′在数组中一定出现在 c 的左侧。也就是说，我们可以从小到大枚举 b，同时从大到小枚举 c，即第二重循环和第三重循环实际上是并列的关系。
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: n = len(nums) nums.sort() ans = list() # 枚举 a for first in range(n): # 需要和上一次枚举的数不相同 if first > 0 and nums[first] == nums[first - 1]: continue # c 对应的指针初始指向数组的最右端 third = n - 1 target = -nums[first] # 枚举 b for second in range(first + 1, n): # 需要和上一次枚举的数不相同 if second > first + 1 and nums[second] == nums[second - 1]: continue # 需要保证 b 的指针在 c 的指针的左侧 while second < third and nums[second] + nums[third] > target: third -= 1 # 如果指针重合，随着 b 后续的增加 # 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环 if second == third: break if nums[second] + nums[third] == target: ans.append([nums[first], nums[second], nums[third]]) return ans
复杂度分析
时间复杂度：O(N^2)，其中 N 是数组nums 的长度。
空间复杂度：O(logN)。我们忽略存储答案的空间，额外的排序的空间复杂度为 O(logN)。然而我们修改了输入的数组nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了nums 的副本并进行排序，空间复杂度为 O(N)。
