如何修改3sum算法使其返回所有和小于等于目标值的三元组

原有代码问题梳理 #

• 目标值硬编码为8，无法灵活适配不同输入需求
• 双指针移动逻辑完全错误：总和大于目标值时错误右移左指针（会让总和更大），总和小于等于目标值时，仅添加当前左右指针的一组结果，漏掉了当前左指针对应的所有右指针区间的合法结果
• return语句缩进错误，放在了第一层for循环内部，仅遍历第一个元素就直接返回结果，无法完成全量遍历
• 存在冗余的else分支，永远不会被触发
• 去重逻辑与指针移动逻辑不匹配，可能遗漏去重场景

修正后代码 #

def triplets(nums, target):
    nums.sort()
    output = []
    n = len(nums)
    for i in range(n - 2):
        # 跳过重复的i元素，保证结果不重复
        if i > 0 and nums[i] == nums[i-1]:
            continue
        left = i + 1
        right = n - 1
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            if current_sum > target:
                # 总和过大，右指针左移缩小总和
                right -= 1
                # 跳过重复的right元素
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
            else:
                # 当前left固定时，[left+1, right]区间所有元素作为第三个数都满足条件
                for k in range(left + 1, right + 1):
                    # 跳过重复值避免重复三元组
                    if k > left + 1 and nums[k] == nums[k-1]:
                        continue
                    output.append([nums[i], nums[left], nums[k]])
                # 左指针右移，遍历下一个左指针位置
                left += 1
                # 跳过重复的left元素
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
    return output

测试验证 #

输入nums = [1,2,3,4,5]，target = 8，调用triplets(nums, 8)得到输出：
[[1,2,3], [1,2,4], [1,2,5], [1,3,4]]，和预期结果完全一致。

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