无需排序查找随机列表两数最短距离，求更快方案及哈希表实现逻辑

• 时间复杂度为O(n²)：列表长度为10000时需要执行1亿次运算，运行效率极低
• 逻辑存在错误：min变量的初始化放在了第一层循环内部，每次遍历新元素x都会重置min值，最终输出的结果仅和最后一个元素的遍历结果相关，计算结果不符合预期

哈希表和本题的核心关联是：Python中的set底层基于哈希表实现，可以在O(1)时间复杂度内判断某个数值是否存在于集合中，不需要遍历整个列表，这是我们优化的核心基础。
不排序的前提下，我们可以用从小到大试探差值的逻辑实现快速查找：

1. 先把列表所有元素存入哈希集合，得到O(1)的查询能力，同时自动去重。如果你的需求是「两个索引不同的元素的最小差值（允许数值相同）」，那么只要len(num_set) < len(L)，就说明存在重复元素，最小差值直接为0，不需要后续计算；如果你的需求是「两个数值不同的元素的最小差值」，则跳过这个判断，直接从d=1开始试探。
2. 从最小的可能差值d=1开始依次递增尝试
3. 对每个d，遍历集合中的每个元素x，判断x + d是否存在于集合中
4. 只要找到任意一组满足条件的x，当前的d就是最小差值，直接终止循环返回结果即可

因为你生成的是大范围随机整数，最小差值通常非常小，这个方法的实际运行速度远高于暴力实现。

import random

# 生成随机列表
L = [random.randrange(1, 100**7) for i in range(100*100)]
num_set = set(L)

# 如果允许相同数值（仅要求索引不同），打开下面的注释即可直接得到结果
# if len(num_set) < len(L):
#     print(0)
#     exit()

min_diff = None
d = 1
while True:
    for x in num_set:
        if x + d in num_set:
            min_diff = d
            break
    if min_diff:
        break
    d += 1

print(min_diff)

如果你的使用场景中最小差值可能很大，这个方法的最坏时间复杂度为O(k*n)，k为最小差值的大小，这种情况下如果允许排序，排序后比对相邻元素的O(nlogn)方案稳定性更高，但在你要求的不排序前提下，上述哈希表方案是最优选择。

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