代码超时怎么改

Question

我的一个朋友取从1到n的所有数字的序列（其中n>0）。
在这个序列中，他选择了两个数字，a和b。
他说a和b的乘积应该等于序列中所有数字的和，不包括a和b。
给定一个数字n，你能告诉我他从序列中排除的数字吗？
该函数接受参数：n（n始终严格大于0），
并返回一个数组或字符串（取决于语言），格式为：[（a，b），…]
将按“a”的递增顺序排序。碰巧有几种可能的（a，b）?
如果找不到可能的数字，函数将返回一个空数组（或空字符串），
这将证明我的朋友没有说实话！
题如上，代码没错但是限制了时间，有些值会超时，请问怎么改

def remov_nb(n):
    res = []
    l = [x for x in range(1, n + 1)]
    for i in l:
        for j in l:
            if i * j == sum(l) - i - j:
                res.append((i,j))
    return res
print(remov_nb(26))

Answer 1

先指出一个错误，条件判断那一行前面加一个j！=i，显然你取的两个数不能一样。

最大的优化点在于把sum（l）放在循环外列表生成后，这样只计算一次，而非n*n次。在我的电脑上，只改这一句，在n=1000的量级，时间减少了70倍。

另外一个地方，你自己应该也发现了，计算结果总是重复的两个，这是因为（i，j）和（j，i）的结果是一样的，优化一下循环，时间还能减少一半。

然后再从数学上考虑一下，sum（l）-i-j的值是有范围的：

max_sum=n*(n+1)/2-1-2
min_sum=n*(n+1)/2-n-(n-1)

那么对于给定的i，j必须不小于min_sum/i，同时不大于max_sum/i，这样又能减少一些循环次数。