有关从函数中删除嵌套的for循环的指南

Question

我正在尝试编写最快的算法，以返回3-2000列表中的“魔术三元组”（即x，y，z，其中z是y的倍数，而y是x的倍数）的数量。排序且唯一的整数。

我还没有制定出一个解决方案，其中不包括具有三个连续的循环，因此为O（n ^ 3）。我在网上看到过一个O（n ^ 2），但是我无法理解它在做什么，因此提交它并不适合。

我的代码是：

def solution(l):
    if len(l) < 3:
        return 0
    elif l == [1,1,1]:
        return 1
    else:
        halfway = int(l[-1]/2)
        quarterway = int(halfway/2)
        quarterIndex = 0
        halfIndex = 0
        for i in range(len(l)):
          if l[i] >= quarterway:
            quarterIndex = i
            break
        for i in range(len(l)):
          if l[i] >= halfway:
            halfIndex = i
            break
        triples = 0
        for i in l[:quarterIndex+1]:
            for j in l[:halfIndex+1]:
                if j != i and j % i == 0:
                    multiple = 2
                    while (j * multiple) <= l[-1]:
                        if j * multiple in l:
                            triples += 1
                        multiple += 1
    return triples  

我花了很多时间手动浏览示例，并删除了列表中不必要部分的循环，但这仍然在大约一秒钟内完成了2,000个整数的列表，而我发现的O（n ^ 2）解决方案完成了同一列表仅需0.6秒-似乎相差很小，但显然这意味着我的列表需要60％的时间。

我是否错过了删除循环之一的明显方法？

[此外，我看到提到制作有向图，并且我看到了希望。我可以使用内置函数从原始列表中创建第一个节点的列表，因此原则上我认为这意味着我可以使用两个for循环制作整个图，然后返回第三个节点列表的长度，但是我命中了一堵墙。没有第三个循环，我似乎无法取得进步！

Answer 1

def num_triples(l):
    n = len(l)
    lower_counts = dict((val, 0) for val in l)
    upper_counts = lower_counts.copy()
    for i in range(n - 1):
        lower = l[i]
        for j in range(i + 1, n):
            upper = l[j]
            if upper % lower == 0:
                lower_counts[lower] += 1
                upper_counts[upper] += 1        

    return sum((lower_counts[y] * upper_counts[y] for y in l))