Leetcode_hot_100 T6

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

题解：首先这道题最容易想到的是暴力解，三重for循环，但是效率太低肯定超时，此时我们试图将其转化为两数之和的问题，即遍历固定x，找x右边的y和z，使y+z=-x。

最优解：不妨先进行排序，然后用双指针方法去找y和z

from typing import List

class Solution:

    def threeSum(self, nums: List[int]) -> List[List[int]]:

        nums.sort()

        result = []

        n = len(nums)  # 提前定义n，减少多次调用len(nums)的开销

        for i in range(n – 2):

            # 额外优化：如果nums[i] > 0，排序后后面的数都≥nums[i]，三数之和不可能为0，直接终止循环

            if nums[i] > 0:

                break

            if i > 0 and nums[i] == nums[i – 1]:

                continue

            target_sum = -nums[i]

            j = i + 1

            k = n – 1

            while j < k:

                current_sum = nums[j] + nums[k]

                if current_sum == target_sum:

                    result.append([nums[i], nums[j], nums[k]])

                    # 只有相等场景下，才需要去重（避免重复三元组）

                    j += 1

                    while j < k and nums[j] == nums[j – 1]:  # 优化条件顺序：先判断j<k

                        j += 1

                    k -= 1

                    while j < k and nums[k] == nums[k + 1]:  # 优化条件顺序：先判断j<k

                        k -= 1

                elif current_sum < target_sum:

                    # 非相等场景：直接移动指针，无需去重

                    j += 1

                else:

                    # 非相等场景：直接移动指针，无需去重

                    k -= 1

        return result