题目
给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：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] 。示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。提示
一句话思路：先排序，固定第一个数，剩下两个数用双指针从两端向中间逼近，同时跳过重复值保证结果不重复。
- 排序后，如果第一个数
> 0，后面都更大，直接结束。 - 固定
i后，用L（i+1）和R（n-1）双指针找和为-nums[i]的两个数，大了 R 左移，小了 L 右移。 - 去重两处：外层
i与上一个相同则跳过；内层找到答案后，把和当前相等的L/R全部跳过。 - 时间复杂度 O(n²)，排序 O(n·logn)。
答案
python
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums) # 数组长度
res = [] # 结果列表
if not nums or n < 3: # 数组为空或长度不足 3，不可能有三元组
return []
nums.sort() # 排序：让双指针有方向可循，也方便去重
res = [] # 结果列表（初始化）
for i in range(n): # 固定第一个数 nums[i]
if nums[i] > 0: # 排序后第一个数都 >0，后面更大，三数和不可能为 0
return res # 直接返回当前结果
if i > 0 and nums[i] == nums[i - 1]: # 与上一个数相同，跳过，避免重复三元组
continue
L = i + 1 # 左指针：从 i 的下一位开始
R = n - 1 # 右指针：从数组末尾开始
while L < R: # 双指针向中间逼近
if nums[i] + nums[L] + nums[R] == 0: # 三数和为 0，找到一组
res.append([nums[i], nums[L], nums[R]]) # 加入结果列表
while L < R and nums[L] == nums[L + 1]: # 跳过重复的左值
L = L + 1
while L < R and nums[R] == nums[R - 1]: # 跳过重复的右值
R = R - 1
L = L + 1 # 两指针各自向内移动一位
R = R - 1
elif nums[i] + nums[L] + nums[R] > 0: # 和太大，右指针左移减小和
R = R - 1
else: # 和太小，左指针右移增大和
L = L + 1
return res # 返回所有不重复的三元组
留言板