例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：

[

  [-1, 0, 1],

  [-1, -1, 2]

]

思路：

首先对数组进行排序，排序后固定一个数 nums[i]，再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[L]和 nums[R]，计算三个数的和 sum 判断是否满足为 0，满足则添加进结果集
如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环
如果 nums[i] == nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过
当 sum == 0 时，nums[L] == nums[L+1] 则会导致结果重复，应该跳过，L++
当 sum == 0 时，nums[R] == nums[R−1] 则会导致结果重复，应该跳过，R−−
时间复杂度：O(n2))，n为数组长度

 

代码如下：

class Solution(object):

    def threeSum(self, nums):

        """

        :type nums: List[int]

        :rtype: List[List[int]]

        """

        nums.sort()

        L, res = len(nums), []

        for i in range(L-2):

            if i > 0 and nums[i] == nums[i-1]:

                continue

            target = -1 * nums[i]

            j,k = i + 1, L - 1

            while j<k:

                if nums[j]+nums[k] == target:

                    res.append([nums[i], nums[j], nums[k]])

                    j = j + 1

                    while j<k and nums[j] == nums[j-1]:

                        j = j + 1

                elif nums[j] + nums[k] < target:

                    j = j + 1

                else:

                    k = k - 1

        return res