【leetcode】剑指 Offer II 007. 数组中和为 0 的三个数（双指针）

剑指 Offer II 007. 数组中和为 0 的三个数

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a ，b ，c ，使得 a + b + c = 0 ？请找出所有和为 0 且 不重复 的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

提示：

• $0<=nums.length<=3000$
• $-10^5<=nums[i]<=10^5$

题解

这道题其实是剑指 Offer II 006. 排序数组中两个数字之和 的进阶版，可以参考上道题的思路来进一步解决这道题。

方法一：穷举

具体实现略。

方法二：固定一个值 + 双指针

这个方法可以先看剑指 Offer II 006. 排序数组中两个数字之和 的【方法三：双指针】
首先把 nums 按从小到大排列，固定第一个值 i，0 - nums[i] 即为上一题的 target，然后剩下两个数的查找方法就用上一题双指针的方法即可。此外，这里还要注意去重的问题，因为题目中要求是 不重复 的三元组。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()  # 从小到大排序
        length = len(nums)
        for i in range(length - 2):
            if i > 0 and nums[i] == nums[i-1]:  # 去重
                continue
            low = i + 1
            high = length - 1
            while low < high:
                if nums[i] + nums[low] + nums[high] == 0:
                    res.append([nums[i], nums[low], nums[high]])
                    while low < high:  # 去重
                        low += 1
                        if nums[low] != nums[low - 1]:
                            break
                    while low < high:  # 去重
                        high -= 1
                        if nums[high] != nums[high + 1]:
                            break
                elif nums[i] + nums[low] + nums[high] > 0:
                    high -= 1
                else:
                    low += 1
        return res

在上一道题中还有个二分查找的方法，不过这题用二分法就需要遍历两次，且去重等条件的实现有些复杂，不推荐使用。