coding = utf-8
'''
Created on 2015年11月9日
@author: SphinxW
'''
# 三数之和
#
# 给出一个有n个整数的数组S，在S中找到三个整数a, b, c，找到所有使得a + b + c = 0的三元组。
# 您在真实的面试中是否遇到过这个题？
# 样例
#
# 如S = {-1 0 1 2 -1 -4}, 你需要返回的三元组集合的是：
#
# (-1, 0, 1)
#
# (-1, -1, 2)
# 注意
#
# 在三元组(a, b, c)，要求a <= b <= c。
#
# 结果不能包含重复的三元组。
class Solution:
"""
@param numbersbers : Give an array numbersbers 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
numbers.sort()
res = []
fsum = numbers[0] + numbers[1] + numbers[2]
for index in range(len(numbers)):
headIndex = 0
tailIndex = len(numbers) - 1
while headIndex < tailIndex:
if headIndex >= index:
break
if tailIndex <= index:
break
sum = numbers[headIndex] + numbers[index] + numbers[tailIndex]
if sum == 0:
res.append(
(numbers[headIndex], numbers[index], numbers[tailIndex]))
headIndex += 1
if sum > 0:
tailIndex -= 1
if sum < 0:
headIndex += 1
res = list(set(res))
return res
