Leetcode 3Sum题解出现多余重复列表 求排查逻辑错误

核心问题梳理 #

• 三数求和逻辑错误：三数之和为0的要求是nums[l] + nums[r] + c = 0，推导可得c = -(nums[l] + nums[r])，你的代码在条件判断和结果拼接时都错误使用了nums[l]+nums[r]作为第三个数，导致输出的三元组本身和就不符合题目要求，比如你输出的[-1,2,1]总和为2，完全不满足要求。
• 双指针逻辑不合理：标准三数之和双指针方案是固定第一个元素，在剩余子区间用左右指针找另外两个数，你的方案直接全局移动左右指针，既会遗漏合法组合，也会因为重复元素多次匹配生成重复三元组，比如输入中有两个-1，左指针两次扫到-1时都会生成相同的[-1,0,1]组合，这就是你输出重复的直接原因。
• 去重代码未转列表：Python3中map()返回的是迭代器对象，直接打印会显示内存地址，需要用list()转成列表才能拿到实际去重后的结果，但事后去重效率远低于生成时主动去重。

修复后的代码 #

class Solution:
    def threeSum(self, nums):
        nums.sort()
        n = len(nums)
        final_list = []
        # 固定第一个数的位置
        for i in range(n):
            # 第一个数大于0直接结束，不可能凑出和为0
            if nums[i] > 0:
                break
            # 跳过重复的第一个数，避免重复三元组
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l = i + 1
            r = n - 1
            target = -nums[i]
            while l < r:
                cur_sum = nums[l] + nums[r]
                if cur_sum == target:
                    final_list.append([nums[i], nums[l], nums[r]])
                    # 跳过左指针重复值
                    while l < r and nums[l] == nums[l+1]:
                        l += 1
                    # 跳过右指针重复值
                    while l < r and nums[r] == nums[r-1]:
                        r -= 1
                    # 移动指针找下一组
                    l += 1
                    r -= 1
                elif cur_sum < target:
                    l += 1
                else:
                    r -= 1
        return final_list

print(Solution().threeSum([-1,0,1,2,-1,-4]))

运行后输出为[[-1, -1, 2], [-1, 0, 1]]，符合题目要求。

关键优化说明 #

• 排序后主动跳过重复元素，从源头避免生成重复三元组，不需要事后再做去重操作，效率更高。
• 固定第一个元素后在剩余区间用双指针扫描，时间复杂度为O(n²)，是三数之和问题的最优通用解法。

内容的提问来源于stack exchange，提问作者Preston_Jarvis