15. 三数之和 （三指针解）

原题：

题目：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum

---

解题思路

一开始想使用暴力解法，时间复杂度接近O(n³)，同时难以消除重复的组合，该方法失败。

后来又想了使用双指针+排序解决，从首尾分别向中间遍历，时间复杂度虽然降低了不少，但是同样难以消除重复的组合，因此该方法也失败。

最后无奈参考了题解，发现需要用到三指针+排序实现。跟我的方法二的思想类似，只不过还需要一个指针来固定一个数，动态的控制另外两个数。后来，按照题解的方法解出来后，仔细想了想，如果求两数之和等于0的所有不重复组合，两指针+排序也是轻松可以实现的。那么推到三数之和，四数之和，是不是需要相对应的指针呢？虽然没有达到对于N数之和证明的实力，不过就先假设这个猜想成立吧。

本题解的关键点：
我总结了一句话，对于去掉重复的组合，最清晰的方法应该就是先排序，然后针对三个数字（三个指针）都需要跳过相邻重复的数字。

时间复杂度平均为O(n²)，空间复杂度为O(1)。

---

代码

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 三指针
        nums.sort()  # 时间杂度为O(NlogN)
        lens = len(nums)
        if lens < 3 or (nums[0] + nums[-1] > nums[-1] or nums[0] + nums[-1] < nums[0]):
            # 不可能有三元组满足a+b+c=0
            return []
        result = []
        for i in range(0,lens-2):
            if i > 0 and nums[i] == nums[i-1]: # 预防第一个数出现重复
                continue
            left, right = i+1, lens-1
            while left < right:
                if nums[i] + nums[left] + nums[right] == 0:
                # 因为两个数字已经能够决定第三个数字了,因此如果第一个数字固定，第二个也相同的话，则说明出现重复，因此在固定第一个数字后，要确保第二个数字不能重复，因此再排序好后需要跳过相同的相邻第二个数字
                    result.append([nums[i], nums[left] ,nums[right]])
                    # 动态修改双指针,对第二个数和第三个数进行预防重复，只需要跳过重复的数字
                    while left < right and nums[left] == nums[left+1]:
                        left += 1
                    while left < right and nums[right] == nums[right-1]:
                        right -= 1
                    # 双指针向往下遍历
                    left += 1
                    right -= 1
                elif nums[i] + nums[left] + nums[right] > 0:
                    right -= 1
                else:
                    left += 1
        return result