谷歌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 Falsedef 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):

    triples_count=0

    p=len(l)

    print l

    for i in xrange(p-2):

        for j in xrange(i+1, p-1):

            if l[j] % l[i] == 0:

                for k in xrange(j+1, p):

                    if l[k] % l[j] == 0:

                        #print l[i], l[j], l[k]

                        triples_count=triples_count+1

    return(triples_count)

Answer 3

删除步骤，因为它会更改数字索引的顺序，因为其中一个约束说 。l=sorted(l)i < j < k

考虑以下情况：

4 2 1

答案应该是，但您的代码将返回。01

关于效率，您可以计算每个数字从右侧除以多少个数字。对于每个计数，如下所示：1,2,3,4,5,6

1 2 3 4 5 6

5 2 1 0 0 0 

对于 ，当你来到 时，已经在缓存的数组中，所以现在你有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

   if number in triplet_map:

       triplets += triplet_map(number)

       continue

   cnt = 0

   for(i = number; i < 1000000; i *= number) 

     if i in map:

         if map(i) > 0: 

           cnt += map(i)

     map(number,map(number) + 1)

   triplets += cnt

   triplet_map(number,cnt)

这样，它就像每个数字的对数时间。没有测试这么多，但似乎有效。