毕达哥拉斯三倍效率

我需要创建一个函数，它接受整数列表并返回列表中是否存在毕达哥拉斯三元组。例如，[3, 5, 7, 4]回报True因为 3, 4, 5 是毕达哥拉斯三元组。到目前为止我有这个（Python）：

def containsPythagoreanTriple(a): 
    for i in xrange(len(a)): #square the numbers
        num = a[i]
        a[i] = num**2
    a = sorted(a)
    for start in xrange(len(a)): #compare every pair
        for i in xrange(start+1, len(a)):
            if a[start] + a[i] in a:
                return True
    return False

有没有办法让它变得更有效率？

就性能而言，该代码中有一些可以改进的地方。

目前的实现是O(N**3) (where N is len(a)），当您检查方格列表是否包含每对项目的每个总和时。会员资格测试list is O(N)并且有O(N**2)配对进行测试。

您可以通过使用来改进这一点set而不是存放物品的清单。测试项目成员资格set is O(1)，所以你会得到一个O(N**2)算法是这样的。

还有一些进一步的变化可能会加快速度，但它们都不会进一步改变渐近复杂性。首先，您不需要调用sorted，因为无论如何您都将测试每对项目。您还可以使用集合理解来进行平方，而不是覆盖原始的a列表。最后，您可以使用itertools.combinations生成你的方块对，并且any在生成器表达式上测试它们的总和是否在集合中。

这是使用相同算法的一些更优化的代码：

import itertools

def containsPythagoreanTriple(a):
    squares = {x*x for x in a} # set comprehension
    return any(x+y in squares for x,y in itertools.combinations(squares))

通过以更基本的方式改变算法，可能还有进一步优化的空间。例如，您不需要测试每一对，因为某些值永远不可能是三角形的“短边”（例如最大值）。您可以过滤传递给的方块itertools.combinations这样它们只包括那些小于或等于max(squares)-min(squares)。我不确定这是否值得，除非您的值列表变得非常大。