leetcode [15] 三数之和

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

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

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

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

[
  [-1, 0, 1],
  [-1, -1, 2]
]

来自leetcode 题解

排序，遍历：

如果当前值大于0，表示后面肯定不会有解了

如果和上一个值相同，表示重复值，跳过，否则会重复

选定第一个值后，对于后面的区间进行双指针遍历，如果和大于0，收缩右指针，如果和小于0，收缩左指针，注意，碰到重复值应该进行跳过，否则会重复

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        result = []
        for i, n in enumerate(nums):
            if n > 0:
                return result
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            low = i + 1
            high = len(nums) - 1
            while low < high:
                if n + nums[low] + nums[high] == 0:
                    result.append([n, nums[low], nums[high]])
                    while low < high and nums[low + 1] == nums[low]:
                        low += 1
                    while low < high and nums[high - 1] == nums[high]:
                        high -= 1
                    low += 1
                    high -= 1
                elif n + nums[low] + nums[high] > 0:
                    high -= 1
                else:
                    low += 1
        return result