一刷~
给你一个整数数组
nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为
0且不重复的三元组。注意：答案中不可以包含重复的三元组。
思路：
最重要的是如何剪枝，对算法加速。
思路1：
对nums数组排序。
遍历nums[i]，寻找index>i的部分中，和为-nums[i]的两个数。可以用left、right指针搜索。
当nums[left]+nums[right]>-nums[i]，right--
当nums[left]+nums[right]<-nums[i]，left++
当nums[left]+nums[right]=-nums[i]，输出nums[i], nums[left], nums[right]，然后left++继续遍历，直至left=right**==>提示超出时间限制**
思路2：改进：
**合理的剪枝**
遍历i和left，i和left遇到和上一次的相同值就跳过，right从n-1开始往前移动（内循环中left增大时，不需要再次便利right右侧的部分）
第一次提交代码：
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
nums.sort()
res = []
for i in range(n-2):
target = -nums[i]
left, right = i+1, n-1
while left < right:
if nums[left] + nums[right] > target:
right -= 1
elif nums[left] + nums[right] < target:
left += 1
else:
if [nums[i], nums[left], nums[right]] not in res:
res.append([nums[i], nums[left], nums[right]])
left += 1
return res第二次提交代码：
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
nums.sort()
res = []
for i in range(n-2):
if i > 0 and nums[i] == nums[i-1]:
continue
target = -nums[i]
left, right = i+1, n-1
for left in range(i+1, right):
if left > i+1 and nums[left] == nums[left-1]:
continue
while left < right and nums[left] + nums[right] > target:
right -= 1
if left == right:
break
if nums[left] + nums[right] == target:
res.append([nums[i], nums[left], nums[right]])
return res
