加速嵌套循环

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集和每个密钥，询问密钥是否小于或等于n/2以及n - key是否也是密钥集中的密钥。

这将是O(n log n)最糟糕的情况，而不是O(n^2)，并显着更快。

当然，break只打破了循环的一个级别，所以通过返回true可以更快地成功。