3sum.py

# coding: utf-8

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
 self.ret = []
 numbers.sort() # 排序后搜索，重点是去重！
 for i in xrange(len(numbers)):
 if i > 0: # 第一个元素已经用过必需跳过
 if numbers[i] == numbers[i - 1]:
 continue
 self.twoSum(numbers, -numbers[i], i + 1, len(numbers) - 1)
 return self.ret
 
 def twoSum(self, numbers, target, start, end):
 while start < end:
 x, y = numbers[start], numbers[end]
 if (x + y) == target:
 self.ret.append([-target, x, y])
 start += 1
 end -= 1
 # 跳过重复元素
 while (start < end) and (numbers[start] == x):
 start += 1
 while (start < end) and (numbers[end] == y):
 end -= 1
 elif (x + y) < target:
 start += 1
 else:
 end -= 1
 return ret

# medium: http://lintcode.com/zh-cn/problem/3sum/