描述

给出一个有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。

结果不能包含重复的三元组。

Python：

第一个想法是利用两数之和的思想，因为abc有顺序之分，所以先将数组排序（这里用的冒泡），再用0减去a的值，就可以把b和c转化为两数之和的问题了。注意判断不能有重复的数组。

class Solution:

    def threeSum(self, numbers):

        p = []

       #

        for i in range(len(numbers)):

            for j in range(i+1,len(numbers)):

                if numbers[i] > numbers[j]:

                    numbers[i], numbers[j] = numbers[j], numbers[i]

        for i in range(len(numbers)-2):

            t1 = 0 - numbers[i]

            q = {}

            for j in range(i+1, len(numbers)):

                t2 = t1 - numbers[j]

                if numbers[j] in q:

                    a = numbers[i]

                    b = t2

                    c = numbers[j]

                    l = (a,b,c)

                    if l not in p:

                        p.append(l)

                else:

                    q[t2] = j

        return p