python-3.x - O(n) 澄清中的 Python 对求和问题

Question

给定一个整数数组，输出总和为特定值 k 的所有唯一对。

这是标准解决方案，在 O(n) 时间内：

    if len(arr) < 2:
        return 

    seen = set()
    output = set()

    for num in arr: 

        target = k - num

        if target not in seen: 
            seen.add(num)

        else:
            output.add((min(num, target), max(num, target))) 


    return print('\n'.join(map(str, list(output))))

关于这个解决方案，我有几个问题：

1）为什么我们使用一个集合来存储数组的可见值？为什么不是清单？这有什么改变吗？

2) 为什么是 min(num, target), max(num, target)？这是为了格式一致还是背后有更深层次的原因？一开始我以为是处理(1,3)&(3,1)这样的重复案例，但是这个解决方案并没有遇到我不认为的情况？

标签： python-3.xlistset

Answer 1

1) Set 是python中检查值是否存在而不存储在这种情况下不需要的重复项的更快方法。
2) 这样做的原因(min(num, target), max(num, target))可能是向输出集添加一个元组，该元组包含 (min, max) 顺序中的两个数字，它将在最后一个打印语句中以更好的格式打印。