Python两数之和：列表遍历写法与集合实现的差异及正确性疑问

你的代码虽然在题目给出的示例下能输出正确结果，但并没有满足题目的附加要求，还存在逻辑漏洞：

• 完全没有达成“仅通过一次遍历完成判断”的目标：你写的循环虽然走了一遍列表，但每次执行(y-i) in x的判断时，Python对列表的成员检查需要从头扫描整个列表，相当于每遍历一个元素，就额外多扫一次全表，整体运行的时间复杂度是O(n²)，当列表长度到几千、几万规模时，运行速度会大幅下降，根本不符合单次遍历的性能要求。
• 存在固定的逻辑bug，会输出错误结果：举个最简单的错例，输入列表为[5]、目标和k=10，你的代码会判断出10-5=5存在于列表中，直接返回True，但实际上列表只有1个元素，根本凑不出两个数相加等于10，这个结果是完全错误的。

用集合存储已遍历元素的写法，刚好针对性解决了上面的问题：

• 集合的底层是哈希表结构，成员检查的时间复杂度是O(1)，配合对原列表的单次遍历，整体只需要*O(n)*的运行时间，真正实现了题目要求的“一次遍历完成判断”，哪怕列表规模很大也能快速得到结果。（如果用普通列表存已遍历的元素，查找速度还是慢，和你原来的写法没有本质区别，用集合就是为了把查找的耗时降下来）
• 逻辑上从根源避免了“自己和自己配对”的错误：集合里存的都是遍历途中经过的位置上的元素，当走到当前元素x时，你检查的是“之前见过的数里，有没有能和x加起来等于k的数”，这时候x还没被放进集合，自然不会把当前元素本身当成配对值。还是拿刚才的单元素错例来说，遍历到5的时候，集合是空的，找不到对应的配对值，最后会返回False，结果是正确的。就算列表里有重复的可配对元素，比如[2,2]、k=4，第一次遍历第一个2时集合为空，把2存进去；第二次遍历第二个2时，检查到集合里已经有之前存的2，返回True，也是完全正确的——毕竟这是两个不同位置的元素，符合两数相加的要求。

• 性能差异：你的写法是两层循环的*O(n²)时间复杂度，没有达到题目的附加要求；集合写法是单循环的O(n)*时间复杂度，是这类问题的最优解法之一。
• 正确性差异：你的写法存在“允许单个元素自我配对”的逻辑漏洞，在单元素列表、元素值刚好是k的一半的单值场景下会输出错误结果；集合写法只在已遍历的元素范围内查找配对值，从逻辑上避免了这类错误。
• 通用性差异：你的代码是硬编码的固定输入，每次换测试用例都要改原代码；集合写法是独立的通用函数，可以传入任意列表和目标和直接调用。

补充：如果想把你原来的代码优化成正确的一次遍历实现，思路和集合版本完全一致：不要每次都在全列表里找配对值，把已经遍历过的元素单独存下来即可。

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