题目描述

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