python - 如何检查 N 是否可以表示为特定列表中其他两个数字的总和

Question

我有一个列表:

l = [1,3,4,6,7,8,9,11,13,...]

和一个数字n。

我如何有效地检查数字 n 是否可以表示为列表 l 中两个数字的总和(允许重复)。

如果数字在列表中，除非它可以表示为两个数字，否则它不算数(例如对于 l = [2,3,4] 3 不算数，但 4 会。

令人尴尬的是，这是我尝试过的:

def is_sum_of_2num_inlist(n, num_list): 

num_list = filter(lambda x: x < n, num_list)

for num1 in num_list:
    for num2 in num_list:
        if num1+num2 == n:
            return True

return False

谢谢

Answer 1

def summable(n, l):
    for v in l:
        l_no_v = l[:]
        l_no_v.remove(v)
        if n - v in l_no_v:
            return True
    return False

编辑:解释...

itertools.cominations 是获得所有可能答案的好方法，但它比这个版本慢 ~4 倍，因为这是一个单一循环，一旦找到可能的解决方案就会退出。

这会遍历 l 中的值，复制 l 并删除 v，这样我们就不会添加 v 自身(即如果 n = 4; l = [2, 1] 则没有误报)。然后从 n 中减去 v，如果该值在 l 中，则有两个数字总和为 n .如果您想返回这些数字而不是返回 True，只需 return n, n - v。