给你一个包含 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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
思路：
看到这道题，第一个想法就是暴力破解，用i，j，k三层循环，然后用if判断语句来解决。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
ans=[]
l=len(nums)
for i in range(l):
for j in range(i+1,l):
for k in range(j+1,l):
if nums[i]+nums[j]+nums[k]==0:
s=sorted([nums[i], nums[j],nums[k]])
if s not in ans:
ans.append(s)
return ans
毫无疑问，超时了！
思路：
然后，又想到一个法子，由于a+b+c=0,将c=-（a+b），通过空间换时间的思路，将所有的a+b的和建立成一个二维数组，再从原nums中寻找有无和-（a+b）相同的数，如果有就输出，可惜磨了一下午也搞不出来这个二维数组，以后有机会再搞（cy）。
然后看了答案的一部分思路，想通过双指针来搞，结果。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
ans=[]
nums.sort()
for i in range(len(nums)):
if i==len(nums)-2:
break
else:
for j in range(i+1,len(nums)):
if j == len(nums) - 1:
break
end=len(nums)-1
while end>j and nums[i]+nums[j]+nums[end]>0:
end-=1
if end==j:
break
if nums[i]+nums[j]+nums[end]==0 and [nums[i],nums[j],nums[end]] not in ans:
ans.append([nums[i],nums[j],nums[end]])
return ans
咋还超时。
接着看看详细的思路。
nums= [-1,0,1,2,-1,-4]
n = len(nums)
nums.sort()
print(nums)
ans=[]
for first in range(n):
# 需要和上一次枚举的数不相同
if first > 0 and nums[first] == nums[first - 1]:
continue
# c 对应的指针初始指向数组的最右端
third = n - 1
target = -nums[first]
# 枚举 b
for second in range(first + 1, n):
# 需要和上一次枚举的数不相同
if second > first + 1 and nums[second] == nums[second - 1]:
continue
# 需要保证 b 的指针在 c 的指针的左侧
while second < third and nums[second] + nums[third] > target:
third -= 1
# 如果指针重合，随着 b 后续的增加
# 就不会有满足 a+b+c=0 并且 b
看了答案后，我悟了，之前我通过判断是否与后一个数字不同，来遍历寻找答案，结果总是少一个答案。
如图。
nums= [-1,0,1,2,-1,-4]
ans=[]
nums.sort()
print(nums)
for i in range(len(nums)):
if i==len(nums)-2:
break
else:
for j in range(i+1,len(nums)):
if j == len(nums) - 1:
break
if nums[j] == nums[j + 1] :
continue
end=len(nums)-1
while end>j and nums[i]+nums[j]+nums[end]>0:
end-=1
if end==j:
break
if nums[i]+nums[j]+nums[end]==0 and [nums[i],nums[j],nums[end]] not in ans:
ans.append([nums[i],nums[j],nums[end]])
print(ans)
后来发现了错误，真是细节。
