找出列表中的配对数

5 投票

2 回答

15004 浏览

提问于 2025-04-18 02:35

假设我们有一个列表 lst = [7,1,5,4,2,3,6]，其中有一些数字对，比如 (7, 2)、(5, 4) 和 (6, 3)，总共有 6 对数字的和是 9。

这里有几点需要注意：
(i) 数字对的顺序很重要。例如，(7, 2) 和 (2, 7) 是两个不同的对。
(ii) 一个数字不能和自己配对。
(iii) 列表中没有重复的元素。

def find_pairs(lst, key):
    count = 0
    if sum(lst[count:count+1]) == key:
        count += 1
        return count
    else:
        return find_pairs(lst[1:],key)

这是我的代码。哪里出错了？我在输入 find_pairs([7,1,5,4,2,3,6], 9) 时得到了 6 的错误。

find_pairs(list(range(1, 100, 2)), 55) #0
find_pairs(list(range(1, 100, 2)), 56) #28

数据结构列表算法数字对配对数

2 个回答

你的代码存在以下问题：

它一次只考虑一个值（lst[i:i+1] 这个切片只包含一个项目，和 [lst[i]] 是一样的）
（修正这个问题后）你的代码只考虑相邻的两个值——在你的例子中，(7, 2) 永远找不到，因为7和2在输入列表中并不相邻
使用递归没有任何必要

这里有一个更高效的版本（时间复杂度是 O(n) 而不是 O(n**2)）：

def find_pairs_count(lst, pair_sum):
    upto = (pair_sum - 1) // 2
    vals = set(lst)
    return 2 * sum(i <= upto and (pair_sum - i) in vals for i in lst)

回答于 2025-04-18 由 Python大师

分享举报

在 itertools 模块中，有一个内置的功能可以做到这一点：

def find_pairs(lst, key):
    return [(a,b) for a,b in itertools.permutations(lst, 2) if a+b==key]

或者，更通用的写法是：

def find_tuples(lst, key, num=2):
    return [i for i in itertools.permutations(lst, num) if sum(i)==key]

你可以这样使用它：

>>> find_tuples(lst, 9)
[(7, 2), (5, 4), (4, 5), (2, 7), (3, 6), (6, 3)]
>>> find_tuples(lst, 9, 3)
[(1, 5, 3), (1, 2, 6), (1, 3, 5), (1, 6, 2), (5, 1, 3), (5, 3, 1), (4, 2, 3), 
 (4, 3, 2), (2, 1, 6), (2, 4, 3), (2, 3, 4), (2, 6, 1), (3, 1, 5), (3, 5, 1), 
 (3, 4, 2), (3, 2, 4), (6, 1, 2), (6, 2, 1)]

回答于 2025-04-18 由 Python大师

分享举报

找出列表中的配对数

2 个回答

撰写回答