python - 加速嵌套循环

Question

我正在做一个关于三角数的挑战。重点是找出任意两个三角形数之和是否等于输入 n。我让它工作了，但显然需要太长时间，他们想要更快的东西。

我编写的方式是将所有三角形数字放入一个列表中，然后循环遍历该列表以检查是否有任何一对数字满足条件。我不知道如何使循环更快，并且阅读这里的类似帖子我不知道如何将其应用于这种情况。

这是代码:

def Triangular(n):
    lst = []
    for i in range(1, n + 1):
        lst.append((i** 2 + i)//2)
    yn = False
    for i in lst:
        for j in lst:
            if i*i + j*j == n:
                yn =  True
                break
            else:
                continue
    return yn

Answer 1

将三角形数的平方放入d̶i̶c̶t̶i̶o̶n̶a̶r̶y集合(不是列表)中。然后遍历 d̶i̶c̶t̶i̶o̶n̶a̶r̶y 集合，对于每个键，询问该键是否小于或等于 n/2 以及 n - key 是否也是 l̶i̶s̶t 中的键设置。

最坏情况是 O(n log n)，而不是 O(n^2)，而且速度明显更快。

当然，break 只会跳出一级循环，因此通过返回 true 可以更快地成功。