15. 三数之和(medium)

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

• show the code:

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n,res = len(nums),[]
        for i in range(n):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l = i+1
            r = n-1
            while l < r:
                s = nums[i]+nums[l]+nums[r]
                if s == 0:
                    res.append([nums[i],nums[l],nums[r]])
                    l += 1
                    r -= 1
                    while nums[l] == nums[l-1] and l < r:
                        l += 1
                    while nums[r] == nums[r+1] and l < r:
                        r -= 1
                elif s < 0:
                    l += 1
                else:
                    r -= 1
        return res

• 此题是2sum的升级版，我们知道2sum的核心思想是利用字典来存储信息，从而优化时间复杂度。

• 3sum中，我们确定一个数，然后去寻找适合它的两个数，这两个数如何快速的寻找呢，我们考虑先对数组排序，排序虽然需要时间，但是可以保持在nlogn的复杂度，而且会大大减少后续的时间。

• 排序之后，我们可以直接取这个数之后的第一个数和整个数组最后一个数，这时其实就是一个a+b = -c的问题了，如果a+b > -c说明大的那个数太大了，我们就将最右边的指针左移，如果a+b < -c说明小的那个数太小了，我们就将左边那个数右移，如果正好满足a+b = -c那我们就将这三个数保存，同时右移和左移，两个指针相撞时，结束循环。

• 如果这么交是AC不了的，因为题目中有要求说：
  注意：答案中不可以包含重复的三元组。
  所以我们要去除重复的数的情况。考虑三个数，分别是第一个我们先确定的数，左边的数和右边的数。

• 对第一个数来说，如果下个数重复，我们直接continue到下一次循环。

• 对左边的数和右边的数来说，处理方式是一样的，我们分别都写一个while循环，如果其下一个数重复，我们不断移动相应的指针，同时这里要注意两个指针不能相撞。（注意，这里只在a+b+c = 0的情况下，因为我们只需要考虑满足条件的三元组即可）