[2025-09-21] Leetcode 15. 三数之和（未答出）

题目

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 。
 
提示：

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

我的代码（Python）

version 1

class Solution:

    def findNextNumIdx(self, nums: List[int], start_idx: int):
        for i in range(start_idx + 1, len(nums)):
            if nums[i] != nums[start_idx]:
                return i
        return -1

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums.sort()
        first_idx = 0
        while first_idx != -1 and first_idx < len(nums):
            second_idx = first_idx + 1
            while second_idx != -1 and second_idx < len(nums):
                target = 0 - nums[first_idx] - nums[second_idx]
                third_idx = second_idx + 1
                while third_idx != -1 and third_idx < len(nums):
                    if nums[third_idx] < target:
                        third_idx = self.findNextNumIdx(nums, third_idx)
                    elif nums[third_idx] == target:
                        result.append([nums[first_idx], nums[second_idx], nums[third_idx]])
                        break
                    else:
                        break
                second_idx = self.findNextNumIdx(nums, second_idx)
            first_idx = self.findNextNumIdx(nums, first_idx)
        return result

暴力算法，虽然有做比较上的优化，但是最终超时

version 2

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        cnt_map = {}
        for num in nums:
            if num in cnt_map:
                cnt_map[num] += 1
            else:
                cnt_map[num] = 1
        keys = list(cnt_map.keys())
        for first_idx in range(len(keys)):
            cnt_map[keys[first_idx]] -= 1
            for second_idx in range(first_idx, len(keys)):
                if cnt_map[keys[second_idx]] <= 0:
                    continue
                cnt_map[keys[second_idx]] -= 1
                target = 0 - keys[first_idx] - keys[second_idx]
                if target in cnt_map and cnt_map[target] > 0 and keys.index(target) >= second_idx:
                    result.append([keys[first_idx], keys[second_idx], target])
                cnt_map[keys[second_idx]] += 1
            cnt_map[keys[first_idx]] += 1
        return result

构建计数map，结果是没错，不过在全0的极大数组上再次超时

version 3

class Solution:

    def findNextNumIdx(self, nums: List[int], start_idx: int, direction: int = 1):
        if direction == 1:
            for i in range(start_idx + 1, len(nums)):
                if nums[i] != nums[start_idx]:
                    return i
        else:
            for i in range(start_idx, -1, -1):
                if nums[i] != nums[start_idx]:
                    return i
        return -1

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums.sort()
        first_idx = 0
        while first_idx != -1 and first_idx < len(nums):
            second_idx = first_idx + 1
            third_idx = len(nums) - 1
            while second_idx != -1 and second_idx < len(nums) and third_idx != -1 and second_idx < third_idx:
                sum = nums[first_idx] + nums[second_idx] + nums[third_idx]
                if sum == 0:
                    result.append([nums[first_idx], nums[second_idx], nums[third_idx]])
                    second_idx = self.findNextNumIdx(nums, second_idx)
                    if second_idx == -1 or second_idx >= len(nums):
                        break
                    third_idx = self.findNextNumIdx(nums, third_idx, -1)
                elif sum > 0:
                    third_idx = self.findNextNumIdx(nums, third_idx, -1)
                else:
                    second_idx = self.findNextNumIdx(nums, second_idx)
            first_idx = self.findNextNumIdx(nums, first_idx)
        return result

放弃自己摸索，参考答案，对第一个版本再次修改。里层不做循环，两边往一起往中间走，直到碰头。满足条件。
其中

                if sum == 0:
                    result.append([nums[first_idx], nums[second_idx], nums[third_idx]])
                    second_idx = self.findNextNumIdx(nums, second_idx)
                    if second_idx == -1 or second_idx >= len(nums):
                        break
                    third_idx = self.findNextNumIdx(nums, third_idx, -1)

这里还加上了一个单独的判断，因为不做判断，两个索引都计算的话，还是会在全0极大数组上超时。

点评

虽然想到了转化成两数和的形式，不过优化仍然不够。
另外比起官方还是啰嗦了不少。