如何在3SUM问题中避免生成重复的三元组组合？

你的朴素解法思路是对的，先排序再三重循环查找，但因为数组里有重复元素，导致会输出重复的三元组。要解决这个问题，可以利用数组已排序的特性，在循环中跳过重复的元素，具体修改如下：

修改后的代码 #

nums = [-1, 0, 1, 2, -1, -4]
nums.sort()
result = []
for i in range(len(nums)):
    # 跳过和前一个i相同的元素，避免重复基准
    if i > 0 and nums[i] == nums[i-1]:
        continue
    for j in range(i+1, len(nums)):
        # 跳过和前一个j相同的元素（且j必须大于i+1，避免跳过i+1的第一个元素）
        if j > i+1 and nums[j] == nums[j-1]:
            continue
        for k in range(j+1, len(nums)):
            if nums[i] + nums[j] + nums[k] == 0:
                triplet = [nums[i], nums[j], nums[k]]
                result.append(triplet)
# 打印最终结果
for t in result:
    print(t)

关键改动说明 #

• 用result列表统一存储结果，避免中途重复输出
• 外层循环i：当i不是第一个元素，且当前元素和前一个元素相等时，跳过该循环，避免以相同的数作为第一个元素生成重复三元组
• 中层循环j：当j不是i的下一个元素（即j > i+1），且当前元素和前一个元素相等时，跳过，避免在同一个i下生成重复的第二个元素组合
• 因为数组已经排序，且跳过了i和j的重复，所以找到的三元组不会重复

运行这段代码后，输出就是你预期的：

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

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