1. 原始题目

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

在真实的面试中遇到过  

2. 解法

分析：此题的难点在于突破时间限制。暴力是3立方复杂度。

一种解法是将数组先排序，然后分别以负数为target，将后面的数组由3数之和变为2数之和问题。

此外如果排序后第一个数大于0，则后续所有数肯定也大于0，这种情况肯定不可能有三数之和=0。

上图为核心思路：Target从最左边向非正数区间移动，对于每个Target取值，都有Head（从target下一位开始）和tail（从尾部开始），当head<tail时，两者相向移动。注意这里可以加入去重操作：例如当tail移到第二个1时，判断其左边也是1，说明这个1不必再看，所以tail应该直接移到0！head原理一样，head每次移动都判断当前head和右边的head取值是否一样，一样则head+=1。其实对于每个target循环取值，固定一个target取值的时候，这时对于后面的所有序列就变成了一个2数之和问题：

target=-4， 则求解-2~6的两数之和为4问题。

target=-2，则求解-1~6的两数之和为2的问题。

target=-1，则求解0~6的两数之和为1的问题。

.......

target =1>0。结束，返回结果并退出。

 

3. 实现

 1 class Solution:
 2     def threeSum(self, nums):
 3         if len(nums)<3: return []
 4         results = []
 5         
 6         L = sorted(nums)  # 排个序，由小到大
 7         i = 0
 8         
 9         for i in range(len(L)):
10             if L[i]>0: break        # 如果首部都走到正数区间了，直接退出
11             if (i>0) and (L[i]==L[i-1]):continue    # 如果当前数和前面的数一样，为了去重复，继续下一个
12             target = 0-L[i]          # target为第i个元素的负数
13             head = i+1               # head从target下一个位置起向右走
14             tail = len(L)-1          # tail从末尾向左走 
15             while(head<tail):        # 当首尾没相遇的时候
16                 if L[head]+L[tail]==target:     # 找到一个三数之和为0的情况
17                     results.append([L[head],L[tail],L[i]])     # 加入结果
18                     
19                     while (head<tail)and(L[head]==L[head+1]):head+=1   # 去重，当前head右移
20                     while (head<tail)and(L[tail]==L[tail-1]):tail-=1   # 去重，当前tail左移
21                     head+=1     # 移到下一位不重复的数
22                     tail-=1     # 移到下一位不重复的数
23                 elif L[head]+L[tail]>target:    # 若两数之和太大，那么tail应该左移一下
24                     tail-=1 
25                 else:                           # 若两数之和太小，那么head应该右移一下
26                     head+=1
27             i+=1
28  
29         return results

 

验证：

1 s = Solution()
2 print(s.threeSum([-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6]))

[[-2, 6, -4], [0, 4, -4], [1, 3, -4], [2, 2, -4], [-2, 4, -2], [0, 2, -2]]