找到访问代码

写一个函数答案(l),它取一个正整数列表l并计算(lst [i],lst [j],lst [k])的“幸运三元组”的数量,其中i <1. j< ķ. l的长度在2到2000之间. l的元素介于1和999999之间.答案符合有符号的32位整数.有些列表是故意生成的,没有任何访问代码来甩掉间谍,所以如果没有找到三元组,则返回0. 例如,[1,2,3,4,5,6]具有三元组：[1,2,4],[1,2,6],[1,3,6],使答案总数为3. 测试用例 输入：
    (int list)l = [1,1,1]
输出：
    (int)1

输入：
    (int list)l = [1,2,3,4,5,6]
输出：
    (int)3

我的尝试

from itertools import combinations

def answer(l):
    if len(l) < 3:
        return 0
    found = 0
    for val in combinations(l,3):
        # Ordering Check
        if (val[0] <= val[1] <= val[2]) != True:
            continue
        # Answer Size Check against size of signed integer 32 bit
        if int(val[0].__str__() + val[1].__str__() + val[2].__str__()) > 2147483647:
            continue
        # Division Check
        if (val[1] % val[1] != 0) or (val[2] % val[1] != 0):
            continue
        # Increment 'found' variable by one
        found += 1
    return found

解决方法:

这是我头顶的解决方案,具有O(n ^ 2)时间和O(n)空间复杂度.我认为有一个更好的解决方案(可能使用动态编程),但是这个可以产生所有组合.

public static int foobar( int[] arr)
{
    int noOfCombinations = 0;
    int[] noOfDoubles = new int[arr.length];

    // Count lucky doubles for each item in the array, except the first and last items
    for( int i = 1; i < arr.length-1; ++i)
    {
        for( int j = 0; j < i; ++j)
        {
            if( arr[i] % arr[j] == 0)
                ++noOfDoubles[i];
        }
    }

    // Count lucky triples
    for( int i = 2; i < arr.length; i++)
    {
        for( int j = 1; j < i; ++j)
        {
            if( arr[i] % arr[j] == 0)
                noOfCombinations += noOfDoubles[j];
        }
    }

    return noOfCombinations;
}