问题 12：寻找目标和的配对

Source: Dev.to

问题描述

编写一个函数，找出列表中所有相加等于给定目标和的唯一数对。
函数应返回一个元组列表，每个元组按升序排列。每个数对只能出现一次。

示例

find_pairs([1, 5, 7, -1, 5], 6)   # → [(1, 5), (-1, 7)]
find_pairs([2, 3, 4, 5], 9)      # → [(4, 5)]

解决方案

Python 实现

def find_pairs(lst, target):
    """
    Finds all unique pairs in the list that sum up to the target.
    Returns a list of tuples sorted within each pair.
    """
    seen = set()
    pairs_found = set()
    for num in lst:
        complement = target - num
        if complement in seen:
            pairs_found.add((min(num, complement), max(num, complement)))
        seen.add(num)
    return list(pairs_found)

# Test cases
print(find_pairs([1, 5, 7, -1, 5], 6))   # Output: [(1, 5), (-1, 7)]
print(find_pairs([2, 3, 4, 5], 9))      # Output: [(4, 5)]

解释

1. 跟踪已出现的数字 – seen 是一个集合，用于存储已经处理过的数字，支持 O(1) 查找。
2. 存储数对 – pairs_found 是一个元组集合。使用集合可以保证重复的数对被忽略。
3. 遍历列表
   • 对每个 num，计算其补数 target - num。
   • 如果补数已经在 seen 中，则找到了一个有效的数对。
   • 使用 min 和 max 将数对按升序加入 pairs_found，保持元组的一致性。
4. 更新 seen – 在检查完补数后，将当前的 num 加入 seen，以便后续元素可以将其作为补数。
5. 返回结果 – 在返回之前将数对集合转换为列表。列表中数对的顺序不保证，但每个数对都是唯一且已排序的。