题目描述
给出一个有n个整数的数组S，在S中找到三个整数a, b, c，找到所有使得a + b + c = 0的三元组。
在三元组(a, b, c)，要求a <= b <= c，结果不能包含重复的三元组。
测试样例
输入:[2,7,11,15]
输出:[]
输入:[-1,0,1,2,-1,-4]
输出:[[-1, 0, 1],[-1, -1, 2]]
思路
将三数之和转换为两数之和求解，两数之和的目标为第三个数的相反数。对数组进行排序，然后依次取出一个数作为固定数，接着在除这个数之外的子序列中拿出头尾两个数，将它们之和与目标比较，若一致则说明找到解，否则缩减子序列的范围继续查找。
具体步骤
1、由于要求最终生成的每个三元组是升序的，因此可以先将数组由小到大进行排序；
2、若排序后数组的第一个元素都大于0，说明不可能存在三数之和为0的情况；
3、否则，遍历数组中的每个数，直到倒数第3个数，将其作为a，当a不是序列中第一个数的时候，要先判断下a是否和位于它前一位的数相同，若是，则进行下一轮循环；
4、将位于a之后的所有数中取出首尾两个数分别作为b和c；
5、将b+c与0-a进行比较，若前者大，则将c前面的一个数（比c小）作为c；若后者大，则将b后面的一个数（比b大）作为b；若两者相等，则找到一个符合要求的三元组(a, b, c)，记录下来；
6、在4中若找到解，由于符合要求的三元组不能重复，因此需要将b向前移动1位和将c向后移动一位。另外，若b和c没有走到重合的位置，且b和它前一位的数相同，则b继续往前走；若c和它后一位的数相同，c也继续往后走；
7、重复5、6直至b和c走到重合的位置；
8、重复3-7直至数组中倒数第3个数也处理完
代码
class Solution:
"""
@param numbers: Give an array numbers of n integer
@return: Find all unique triplets in the array which gives the sum of zero.
"""
def threeSum(self, numbers):
# write your code here
if not numbers:
return []
# 先进行排序
seq = sorted(numbers)
# 若序列中的最小数大于0，
# 则不可能有三数之和为0的情况
if seq[0] > 0:
return []
ans = []
for i in range(len(seq) - 2):
# 去重
if i > 0 and seq[i] == seq[i - 1]:
continue
a = seq[i]
target = 0 - a
j, k = i + 1, len(seq) - 1
while j < k:
'''去重'''
if j - i > 1 and seq[j] == seq[j - 1]:
j += 1
continue
b, c = seq[j], seq[k]
if b + c > target:
k -= 1
elif b + c < target:
j += 1
else:
ans.append([a, b, c])
'''由于结果不能包含重复的三元组，因此b和c的位置需要移动'''
j += 1
k -= 1
'''去重'''
while j < k and seq[j] == seq[j - 1]:
j += 1
while j < k and seq[k] == seq[k + 1]:
k -= 1
return ans
附：方法2 —— 不需排序，代码量较少但空间复杂度更高
思路
实质也是将三数之和转化为两数之和。
不同的是，直接遍历序列中的每个数，直到倒数第3个数，将其作为a，然后遍历a之后的每个数，作为b，看看 c = 0 - a - b 是否在之前的遍历过程中遇到过，若是则说明找到一组解；否则将b记录下来，这样，遍历到后面的b时，此时的b就有可能成为后续的c = 0 - a - b。
代码
from collections import defaultdict
class Solution:
"""
@param numbers: Give an array numbers of n integer
@return: Find all unique triplets in the array which gives the sum of zero.
"""
def threeSum(self, numbers):
# write your code here
if not numbers:
return []
ans = []
for i in range(len(numbers) - 2):
a = numbers[i]
# b + c = 0 - a
target = 0 - a
residual = defaultdict(bool)
for j in range(i + 1, len(numbers)):
b = numbers[j]
c = target - b
# 把此时的c当作以前的b,
# 看是否出现过
if residual.get(c):
seq = sorted([a, b, c])
# 不能包含重复的三元组
if seq not in ans:
ans.append(seq)
else:
# 由于结果不能包含重复的三元组，
# 因此是有当没有找到满足条件的方案时
# 才把此时的b记录下来
residual[b] = True
return ans
