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

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

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

解法一：排序+双指针

排序的目的是为了在自左向右遍历nums[first], nums[second], nums[third]，能够方便的跳过重复元素。当nums[first]确定时，nums[second]与nums[third]可以通过双指针向两边相向移动的方式来找到target = -nums[first]。注意由于这题与两数之和那题不一样，会存在多组解，不唯一，因此second需要遍历全部first+1 ~ n - 1，third从n-1位置向左移动。

  1. class Solution:
  2.     def threeSum(self, nums: List[int]) -> List[List[int]]:
  3.         n = len(nums)
  4.         nums.sort()
  5.         ans = list()
  7.         # 枚举 a
  8.         for first in range(n):
  9.             # 需要和上一次枚举的数不相同
  10.             if first > 0 and nums[first] == nums[first - 1]:
  11.                 continue
  12.             # c 对应的指针初始指向数组的最右端
  13.             third = n - 1
  14.             target = -nums[first]
  15.             # 枚举 b
  16.             for second in range(first + 1, n):
  17.                 # 需要和上一次枚举的数不相同
  18.                 if second > first + 1 and nums[second] == nums[second - 1]:
  19.                     continue
  20.                 # 需要保证 b 的指针在 c 的指针的左侧
  21.                 while second < third and nums[second] + nums[third] > target:
  22.                     third -= 1
  23.                 # 如果指针重合，随着 b 后续的增加
  24.                 # 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
  25.                 if second == third:
  26.                     break
  27.                 if nums[second] + nums[third] == target:
  28.                     ans.append([nums[first], nums[second], nums[third]])
  30.         return ans

另一种书写方式。其中从11行开始与TwoSum一样，是两端双指针。区别在于TwoSum在遇到target后直接就退出了，二ThreeSum中需要继续向后移动j。也正因为解不唯一，因此移动j和k都需要用while来跳过移动方向上的重复元素。

  2. class Solution:
  3.     def threeSum(self, nums: List[int]) -> List[List[int]]:
  4.         n = len(nums)
  5.         nums.sort()
  6.         ans = []
  7.         for i in range(n):
  8.             if i > 0 and nums[i] == nums[i - 1]:
  9.                 continue
  10.             j, k, target = i + 1, n - 1, -nums[i]
  11.             while j < k:
  12.                 if nums[j] + nums[k] == target:
  13.                     ans.append([nums[i], nums[j], nums[k]])
  14.                     # 跳过重复nums[j]后尝试下一个
  15.                     while j < k and nums[j + 1] == nums[j]:
  16.                         j += 1
  17.                     j += 1
  18.                 elif nums[j] + nums[k] > target:
  19.                     # 跳过重复nums[j]后尝试下一个
  20.                     while j < k and nums[k - 1] == nums[k]:
  21.                         k -= 1
  22.                     k -= 1
  23.                 else:
  24.                     # 跳过重复nums[k]后尝试下一个
  25.                     while j < k and nums[j + 1] == nums[j]:
  26.                         j += 1
  27.                     j += 1
  28.         return ans