数组缺失元素查找：两段代码结果正确但耗时差异原因咨询

两段代码逻辑一致——都是遍历1到N的所有数，找出不在输入数组里的那个，但效率天差地别，问题出在**「判断元素是否存在」的操作效率上**：

• 第一段代码用普通数组（列表）的in操作：
  每次判断I not in array时，程序会从数组第一个元素开始逐个比对，直到找到目标元素或者遍历完整个数组。这个操作的时间成本和数组长度成正比（O(N)）。再加上外层遍历1到N的循环（O(N)），整体时间复杂度是O(N²)。当N很大时（比如十万、百万级别），这种嵌套的线性操作会产生巨量计算，自然耗时很长，甚至超时。

• 第二段代码先把数组转成集合再做查询：
  集合（Set）的底层是哈希表结构，它会给每个元素分配唯一的哈希值，查询元素是否存在时，直接通过哈希值定位，不需要遍历整个集合，平均时间成本是常数级（O(1)）。转集合的过程只需要遍历一次数组（O(N)），之后的循环查询每个数都是O(1)，整体时间复杂度是O(N)。不管N多大，计算量都和N成正比，效率比第一段代码高几个数量级，所以能轻松通过所有测试用例。

额外提一句：如果追求极致效率，还可以用数学方法——用1到N的求和公式（N*(N+1)/2）减去数组所有元素的和，结果就是缺失的数，时间复杂度同样是O(N)，代码会更简洁。

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