如何解决closestNumbers函数的TLE问题？求代码优化建议

给定整数数组numbers，实现函数closestNumbers(numbers)：找出数组中任意两个整数的最小绝对差，并输出所有具有该最小差值的整数对。输出的数对pairs[i,j]需先按i升序排列，再按j升序排列。

当前代码通过部分测试，但多数隐藏测试出现**TLE（超时）**错误，怀疑是嵌套循环导致，求优化建议或TLE原因分析。

原代码 #

def closestNumbers(numbers):
    numbers.sort()
    d=abs(numbers[0]-numbers[1])
    ans=[]

    for j in range(len(numbers)):
        for i in range(j+1, len(numbers)):
            res_1=abs(numbers[j]-numbers[i])
            if (res_1 == d):
                ans.append(numbers[j])
                ans.append(numbers[i])    
            elif (res_1<d):
                d=res_1
                ans=[numbers[j],numbers[i]]
            
    
    for k in range (0, len(ans), 2):
        print (ans[k], ans[k+1])
        
    return 0

TLE原因分析 #

你的代码采用两层嵌套循环遍历所有数对，时间复杂度为O(n²)。当数组规模较大（比如n=10^5）时，运算量会呈指数级增长，直接超出时间限制。

关键误区：数组排序后，最小绝对差必然出现在相邻元素之间。因为排序后数组是升序排列，任意非相邻元素的差值（如a[i]和a[i+2]）等于两个相邻差值的和，必然大于等于其中更小的那个相邻差值。因此完全不需要遍历所有数对，只需检查相邻元素即可。

优化方案 #

优化思路 #

1. 先对数组排序（时间复杂度O(n log n)，是排序算法的固有开销，远低于O(n²)）
2. 一次遍历数组，计算每对相邻元素的差值，记录最小差值
3. 再次遍历数组，收集所有差值等于最小差值的相邻数对
4. 输出结果（排序后的相邻数对天然符合i升序、j升序的要求）

优化后代码 #

def closestNumbers(numbers):
    numbers.sort()
    min_diff = float('inf')
    # 第一次遍历：找出最小差值
    for i in range(len(numbers)-1):
        diff = numbers[i+1] - numbers[i]  # 排序后无需abs，直接后减前
        if diff < min_diff:
            min_diff = diff
    # 第二次遍历：收集所有符合条件的数对
    result = []
    for i in range(len(numbers)-1):
        if numbers[i+1] - numbers[i] == min_diff:
            result.append((numbers[i], numbers[i+1]))
    # 输出结果
    for pair in result:
        print(pair[0], pair[1])
    return 0

优化点说明 #

• 时间复杂度从O(n²)降至O(n log n)（排序占主要开销，两次线性遍历可忽略）
• 排序后相邻元素差值无需abs计算，减少运算开销
• 分两次遍历逻辑清晰，也可合并为一次遍历（边找最小差边临时记录数对，发现更小差值时清空记录重新收集），性能差异可忽略

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