难度: Medium
给定一个包含 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注意：本题与主站 15 题相同：https://leetcode-cn.com/problems/3sum/
运行时间: 220 ms
内存: 18.6 MB
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
nums.sort()
ans = []
for i in range(n - 2):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
l = i + 1
r = n - 1
target = - nums[i]
while l < r:
tmp = nums[l] + nums[r]
if tmp == target:
ans.append([nums[i], nums[l], nums[r]])
while l < r and nums[l + 1] == nums[l]:
l += 1
l += 1
while l < r and nums[r - 1] == nums[r]:
r -= 1
r -= 1
elif tmp > target:
r -= 1
else:
l += 1
return ans
此题解采用排序加双指针的方法解决三数之和问题。首先对数组进行排序，然后使用外层循环遍历每个数作为可能的三元组中的第一个数。对于每个选定的第一个数，使用内层的双指针来查找剩余两个数。如果三个数的和为零，则记录这个组合。为了避免重复的三元组，每次在找到有效的三元组后，需要跳过相同的数。同时，如果当前的数大于0，则可以直接终止循环，因为不可能再找到和为零的三元组。
时间复杂度: O(n^2)
空间复杂度: O(1)
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
nums.sort() # 对数组进行排序
ans = [] # 用于存放结果的列表
for i in range(n - 2): # 遍历到倒数第三个元素即可
if nums[i] > 0:
break # 如果当前数字大于0，终止循环
if i > 0 and nums[i] == nums[i - 1]:
continue # 跳过重复的数字，避免重复解
l = i + 1 # 左指针
r = n - 1 # 右指针
target = -nums[i] # 目标值为当前数的相反数
while l < r: # 双指针遍历
tmp = nums[l] + nums[r] # 计算两指针指向值的和
if tmp == target: # 如果和为目标值
ans.append([nums[i], nums[l], nums[r]]) # 添加到结果中
while l < r and nums[l + 1] == nums[l]:
l += 1 # 跳过重复值
l += 1
while l < r and nums[r - 1] == nums[r]:
r -= 1 # 跳过重复值
r -= 1
elif tmp > target:
r -= 1 # 和大于目标值，移动右指针
else:
l += 1 # 和小于目标值，移动左指针
return ans # 返回结果列表
在排序后的数组中，一旦第一个数（即最小数）大于0，那么后面所有的数也都将大于0。因为三数之和要求的是和为0，所以当三个正数相加时，其结果必定大于0，不可能等于0。因此，当遍历到第一个数大于0时，可以肯定后续不会有任何三个数相加等于0的情况，直接终止循环是合理的。
在双指针策略中，当左右指针指向的元素的和小于目标值时，我们需要增加和的值以接近目标值。由于数组已经排序，右侧的指针指向的元素值较大，左侧的指针指向的元素值较小。因此，为了增加和的值，我们应该将左指针向右移动（即指向一个更大的值），而移动右指针（指向更小的值）会导致和的值减小，远离目标值。
在找到一个有效的三元组后，为避免重复解，需要跳过所有与当前左指针或右指针值相同的元素。实现方法是在每次找到符合条件的三元组后，对左指针进行循环直到指向的下一个数与当前数不同，同理对右指针也做相同的处理。这样的跳过是在已经找到一个有效解之后进行的，因此不会漏掉任何解。此外，外层循环中也同样跳过了与前一个数相同的数，确保了每种可能的起始数只被使用一次，从而避免了从不同位置开始但内容相同的重复三元组。