Python 3中List与Set的时间复杂度差异及代码超时原因解析

这问题我之前帮朋友排查过类似的，本质就是List和Set在成员查找这个操作上的效率天差地别，咱们一步步拆解：

核心差异：时间复杂度 #

• 对于Python的list，当你执行x in A时，它会从第一个元素开始逐个遍历对比，直到找到匹配项或者遍历完整个列表。这个操作的时间复杂度是 O(k)（k是列表的长度）。如果测试用例里A、B的规模很大（比如10^5级别的元素），那每次查找都要跑十万次，再循环arr里的十万个元素，总运算量直接爆炸，不超时才怪。
• 而Python的set，成员查找的平均时间复杂度是O(1)。不管set里有多少元素，每次查找几乎都是常数时间，效率拉满，这也是为什么你的set版本能顺利通过所有测试用例。

工作原理对比 #

List的底层逻辑 #

Python的列表是动态数组，元素在内存里是连续存储的。判断元素是否存在时，没有任何捷径——就像你在一本没有目录的书里找某个词，只能一页一页翻，书越厚（列表越长），找起来越慢。

Set的底层逻辑 #

Set的核心是哈希表（Hash Table）：

1. 当你往set里加元素时，Python会先计算这个元素的哈希值（一个唯一标识的整数），然后根据哈希值把元素放到对应的“存储桶”里。
2. 当你判断x in set时，先计算x的哈希值，直接定位到对应的桶，然后只需要检查这个桶里的元素（因为哈希冲突概率极低，桶里通常只有1个或几个元素），就能快速得出结果。
   相当于给每本书贴了专属标签，找的时候直接按标签找对应的书架，不用翻整本书，速度自然快得多。

结合你的代码分析 #

假设测试用例里：

• arr有10^5个元素

• A和B各有10^5个元素

• List版本：每次循环要做两次O(10^5)的查找，总操作次数是 10^5 * (10^5 + 10^5) = 2*10^10 次——这个量级的运算在HackerRank的时间限制里必然超时。

• Set版本：每次循环是两次O(1)的查找，总操作次数是 10^5 * 2 = 2*10^5 次——完全在时间允许范围内，所以能顺利通过所有测试用例。

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