题目链接:Hot100 - 15.三数之和
题目背景
给你一个整数数组 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 。题目规模
- 3 <= nums.length <= 3000
- -10^5 <= nums[i] <= 10^5
解题思路
题目要找的是满足条件的三元组，且三元组当中为具体的值，故数组的下标并不重要，排序不会影响最后的结果，可以先排序。
要找三个数组下标i,j,k，使得： \[ nums[i] + nums[j] + nums[k] = 0 \] 可以依次固定数组中的每一个数，再从该数的右边找到两个数，使其相加满足条件，这样就将题目转换成了target为nums[i]的两数之和，如图所示:
具体的实现思路如下:
从左往右遍历排序后的数组，将当前遍历到的值固定，记指针为i
从子数组[i + 1,len(nums) - 1]中找到两个指针j、k,使得: \[ nums[j] + nums[k] = -nums[i] \]
排序后的数组具有单调性：
- 当nums[i] + nums[j] + nums[k] < 0时，需要整体值增加，右移j指针
- 当nums[i] + nums[j] + nums[k] > 0时，需要整体值减小，左移k指针
- 当nums[i] + nums[j] + nums[k] = 0时，找到了一组可行的答案，进入下列步骤
由于题目要求答案中不可以包含重复的三元组，故每一次遍历前和找到符合题意的解后还需要将指针移动到特定的位置，具体的步骤如下:
- 在遍历前，若当前固定值和上一个固定值相同，可以直接跳过这次遍历
- 找到符合题意的答案后，将j和k分别移动到与当前指向元素不同的的第一个元素
总结排序后的两步:
1.依次固定每个值，将题目转换为两数之和，从当前固定值之后找到两个元素，使其形成符合题意的三元组
2.通过移动指针进行去重操作
循环上述两步即可找到所有答案。
思路补充
Q：为什么只用从当前固定值的右边找两个元素，而不用再从左边找了?
A：因为在之前的遍历中就已经把所有包含左边元素的解加入到了答案列表。
Q：为什么找到符合题意的答案后，要将j和k分别移动到与当前指向元素不同的的第一个元素？
A：对于数组[a,b,b,c,e,d,d]，设有 a + b + d = 0，若仅仅只是简单移动两个指针，将会重复加入答案[a,b,d]，故需要将两个指针分别移动到c和e，以确保不会重复。
Q：在遍历前，若当前固定值和上一个固定值相同，可以直接跳过这次遍历？
A：由于数组已经排序完毕，故相同的元素将会挨在一起。假设存在重复元素a，当固定到第一个a时，由于是从其之后找剩下两个符合题意的元素，此时分为两种情况：
三元组只包含一个a。
三元组包含多个a。若a不等于0，则三元组最多包含两个a
对于第一种情况，将第一个a之后的其它a当作固定值，得到的答案和第一个a当作固定值的答案是完全相同的。
对于第二种情况，将第一个a之后的其它a当作固定值，得到的答案可能会因为在它之后a的数量不够，而少了一种或两种解。
换言之，无论是哪种情况，将之后的a当作固定值得到的答案的集合只不过是将第一个a当作固定值得到的答案的集合的子集罢了，故可以直接跳过重复值的遍历。
具体代码
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
#如果最小的三个数的和都大于0，那么无解
if nums[0] + nums[1] + nums[2] > 0:
return []
#如果最大的三个数的和都小于0，那么无解
if nums[-1] + nums[-2] + nums[-3] < 0:
return []
ans = []
#固定到len(nums) - 2，因为最后两个元素凑不出三元组
for i in range(len(nums) - 2):
#重复元素直接跳过判断
if i > 0 and nums[i] == nums[i - 1]:
continue
j = i + 1
k = len(nums) - 1
#转为两数之和
while j < k:
#说明小了
if nums[i] + nums[j] + nums[k] < 0:
j += 1
#说明大了
elif nums[i] + nums[j] + nums[k] > 0:
k -= 1
else:
ans.append([nums[i],nums[j],nums[k]])
#找到和左指针相同的最后一个元素
while j < k and nums[j + 1] == nums[j]:
j += 1
#找到和右指针相同的最后一个元素
while j < k and nums[k - 1] == nums[k]:
k -= 1
#移动到不同元素的位置
j += 1
k -= 1
return ans
复杂度分析
- 时间复杂度：O（n²）。每次循环遍历的长度和为 \[ （n - 1） +（ n - 2） +（ n - 3） +.... + 2， \]
故时间复杂度为O（n²）。
- 空间复杂度：O（1）
