在python中使用嵌套循环时，有没有提高性能的技巧

Question

所以，我做了这个练习，在那里我会收到一个整数列表，并且必须找到多少和对是60的倍数

例如：

输入：list01 = [10,90,50,40,30]

结果=2

说明：10+50、90+30

例2：

输入：list02 = [60,60,60]

结果=3

说明：list02[0] + list02[1], list02[0] + list02[2], list02[1] + list02[2]

看起来很简单，下面是我的代码：

def getPairCount(numbers):
    total = 0
    cont = 0
    for n in numbers:
        cont+=1
        for n2 in numbers[cont:]:
            if (n + n2) % 60 == 0:
                total += 1
    return total

但是，它工作正常，因为一个超过100k+数字的大输入需要很长时间才能运行，我需要能够在8秒内运行，关于如何解决这个问题的任何提示

使用我不知道的另一个lib，或者在没有嵌套循环的情况下能够解决这个问题

Answer 1

这里有一个简单的解决方案，应该非常快（它在O（n）时间内运行）。它利用了以下观察结果：我们只关心mod 60的每个值。例如，23和143实际上是相同的

因此，我们没有对列表进行O（n**2）嵌套传递，而是计算每个值的数量，mod 60，因此我们计算的每个值都在0-59范围内

当我们有计数时，我们可以考虑总和为0或60的对。工作的配对是：

0 + 0
1 + 59
2 + 58
...
29 + 31
30 + 30

在此之后，顺序颠倒，但我们只 我想数一次每一对

值相同的情况有两种： 0+0和30+30。对于其中的每一个，数字 对的数目是(count * (count - 1)) // 2。注意 这在计数为0或1时有效，因为在这两种情况下 我们正在乘以零

如果两个值不同，则 案件只是数量的乘积

代码如下：

def getPairCount(numbers):
    # Count how many of each value we have, mod 60

    count_list = [0] * 60
    for n in numbers:
        n2 = n % 60
        count_list[n2] += 1

    # Now find the total

    total = 0

    c0 = count_list[0]
    c30 = count_list[30]

    total += (c0 * (c0 - 1)) // 2
    total += (c30 * (c30 - 1)) // 2

    for i in range(1, 30):
        j = 60 - i
        total += count_list[i] * count_list[j]

    return total

这在O（n）时间内运行，因为我们对输入值列表进行了初始一次性传递。最后的循环只是从1到29进行迭代，并且不是嵌套的，因此它应该几乎立即运行