谷歌Foobar：次优解中的逻辑错误

Question

问题

编写一个函数 answer（l），该函数采用正整数列表 l 并计算 （lst[i]， lst[j]， lst[k]） 的“幸运三元组”的数量，其中 i < j < k。l 的长度介于 2 和 2000 之间（含）。l 的元素介于 1 和 999999之间。答案适合有符号的 32 位整数。一些列表是故意生成的，没有任何访问代码来甩掉间谍，因此如果没有找到三元组，则返回0。

幸运三元组基本上是元组（x，y，z），其中x除以y，y除以z，例如（1，2，4）。

例如，[1， 2， 3， 4， 5， 6]具有三元组：[1， 2， 4]，[1， 2， 6]，[1， 3， 6]，使答案总计3。

我的代码

def isLuckyTriple(a,b,c):

    if b%a==0 and c%b==0:

        return True

    return False

def solution(l):

    count=0

    l=sorted(l)

    for i in range(len(l)-2):

        for j in range(i+1,len(l)-1):

            for k in range(j+1,len(l)):

                if isLuckyTriple(l[i],l[j],l[k]):

                    count+=1

    return count

我的问题

我已经查看了一些关于这个问题的堆栈溢出答案。我知道如何以不同和更优化的方式做到这一点。唯一的问题是，我的上述代码只通过了5个给定测试用例中的2个测试用例。我想了解我在上面的代码中做错了什么。我更感兴趣的是找出我的错误，而不是以更好的方式去做。

如果您不认为代码不正确，那么它是否因为解决方案非常慢而使测试用例失败？

任何帮助将不胜感激。

Answer 1

每个问题都有时间限制，我认为大约是15秒。据我所知，所有测试用例在验证时并行运行，如果超过15秒，测试用例将失败。具有O（n^3）时间复杂度肯定会使测试用例失败。

Answer 2

def answer(l):&nbsp; &nbsp; triples_count=0&nbsp; &nbsp; p=len(l)&nbsp; &nbsp; print l&nbsp; &nbsp; for i in xrange(p-2):&nbsp; &nbsp; &nbsp; &nbsp; for j in xrange(i+1, p-1):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if l[j] % l[i] == 0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for k in xrange(j+1, p):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if l[k] % l[j] == 0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; #print l[i], l[j], l[k]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; triples_count=triples_count+1&nbsp; &nbsp; return(triples_count)

Answer 3

删除步骤，因为它会更改数字索引的顺序，因为其中一个约束说 。l=sorted(l)i < j < k考虑以下情况：4 2 1答案应该是，但您的代码将返回。01关于效率，您可以计算每个数字从右侧除以多少个数字。对于每个计数，如下所示：1,2,3,4,5,61 2 3 4 5 65 2 1 0 0 0&nbsp;对于 ，当你来到 时，已经在缓存的数组中，所以现在你有2个三元组添加到最终答案中。当你来到时，你会得到三胞胎，所以=。1222132+13时间复杂度：O（n^2）空间复杂度：O（n）因为，问题说，我认为你可以走阶乘的方式。The elements of l are between 1 and 999999 inclusive首先收集映射中的所有值计数。现在，对每个数字进行每个倍数，并将三元组从最后一个添加到第一个。如下图所示：triplet_map = {}map = {}for every number in array: # from last to first&nbsp; &nbsp;if number in triplet_map:&nbsp; &nbsp; &nbsp; &nbsp;triplets += triplet_map(number)&nbsp; &nbsp; &nbsp; &nbsp;continue&nbsp; &nbsp;cnt = 0&nbsp; &nbsp;for(i = number; i < 1000000; i *= number)&nbsp;&nbsp; &nbsp; &nbsp;if i in map:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if map(i) > 0:&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;cnt += map(i)&nbsp; &nbsp; &nbsp;map(number,map(number) + 1)&nbsp; &nbsp;triplets += cnt&nbsp; &nbsp;triplet_map(number,cnt)这样，它就像每个数字的对数时间。没有测试这么多，但似乎有效。