如何简化从整数列表移除无法由另一列表两数之和构成的元素

问题描述 #

给定整数列表a和列表b，需从a中移除所有无法由b中任意两个整数之和构成的元素。例如当a=[3,19,20]、b=[1,2,17]时，期望结果为[3,19]。

我尝试用嵌套循环实现，但被break和continue的语法逻辑弄混，现有代码如下：

def myFunction(list_a, list_b):
    for i in list_a:
        for a in list_b:
            for b in list_b:
                if a + b == i:
                    break
            else:
                continue
            break
        else:
            continue
        list_a.remove(i)
    return list_a

希望能得到更简洁易懂的实现方法。

简洁易懂的实现方案 #

其实我们可以换个思路，先提前算出b中所有两数之和的集合，这样后续判断a中的元素是否符合条件就会非常高效，而且代码可读性也强很多。

核心思路 #

1. 先生成b中所有两个元素之和的集合（用集合是因为集合的查找时间复杂度是O(1)，比列表快很多）
2. 遍历a中的每个元素，只保留那些存在于这个和集合中的元素

实现代码 #

def filter_list_a(list_a, list_b):
    # 生成所有b中两数之和的集合
    sum_pairs = {x + y for x in list_b for y in list_b}
    # 筛选list_a中属于sum_pairs的元素
    return [num for num in list_a if num in sum_pairs]

效果验证 #

用你给出的例子测试：

a = [3,19,20]
b = [1,2,17]
print(filter_list_a(a, b))  # 输出: [3, 19]

完全符合预期结果~

对比原代码的优势 #

• 可读性拉满：逻辑清晰，两步操作一目了然，再也不用纠结嵌套循环里绕来绕去的break和continue
• 效率更高：集合查找的速度远快于嵌套循环的多次判断，尤其是当b的元素较多时，性能优势会非常明显
• 避免遍历修改原列表的坑：原代码中直接在遍历list_a的时候执行remove操作，很容易导致遍历异常（比如跳过某些元素），而新代码是生成一个新列表返回，安全又稳妥

另外，如果你需要保留原列表不被修改，这个实现天然就满足，因为我们没有对输入的list_a做任何修改，只是返回了筛选后的新列表。

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