问题

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。LeetCode原题入口

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

思路

如果简单采用暴力遍历的方式，时间复杂度为$ O(n^3) $，时间上肯定无法通过。可先对数组进行排序，时间复杂度为$ O(n\log n) $，接着从数组第一个数开始遍历，在剩下的数中取2数之和，正好等于第一个数的相反数，这样3者之和正好为0。

设置第一个指针遍历数组，假设遍历到的当前数为x，则要找的2数之和target=-x，由于数组已经经过排序，后面2数可再用2个指针表示，1个指向第1个数的后一个数，也就是正好大于x的数，另1个指向数组最后一位，也就是最大的那个数。计算2个指针所指向数字之和，如果结果大于target，说明结果偏大，将第2个指针向左移动；如果结果小于target，将第1个指针向右移动，使结果偏大；如果相等，说明符合条件，将数字收纳到结果集里面。
最后，由于题目不允许重复，这3个指针如果移动过程中，碰到和上一个数字一样，则直接跳过，时间复杂度为$ O(n^2) $。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def threeSum(self, nums: List[int]) -> List[List[int]]:
        res=[]
        nums=sorted(nums)
        for i in range(len(nums)):
            if i>0 and nums[i]==nums[i-1]:
                continue
            target=-nums[i]
            j,k=i+1,len(nums)-1
            while j<k:
                if nums[j]+nums[k]>target:
                    k-=1
                elif nums[j]+nums[k]<target:
                    j+=1
                else:
                    if nums[j]+nums[k]==target:
                        res.append([nums[i],nums[j],nums[k]])
                        j+=1
                        k-=1
                    while j<k and nums[j]==nums[j-1]:
                        j+=1
                    while j<k and nums[k]==nums[k+1]:
                        k-=1
        return res