python - 加零的组合

Question

给定五个排序列表:List1、List2、List3、List4、List5，每个列表的长度为 n。如果有任何 5 (int) 个数字(每个列表中有 1 个)，则总和为零返回 true。我的目标是确保算法是 O(n)。在我的脑海中，我可以想到创建一个带有 sum 的 HashMap 5 个链接列表或评估 5 个列表，例如 [o(n*n*n*n*n)]。我正在寻找优化或降低复杂性的方法，但我被困住了。

我的 Python 代码:

def getIndicesFromFiveArrays(List1,List2,List3,List4,List5,t):
    a,b,c,d,e=0,0,0,0,0
    while(List1[a]+List2[b]+List3[c]+List4[d]+List5[e]!=t):
        b=b+1
        if b==len(List2):
            return (-1,-1)
        if List1[a]+List2[b]+List3[c]+List4[d]+List5[e]<t:
            a=a+1
            b=b-1
        c=c-1
        d=d-1
        e=e-1
            if a==len(List1):
                return (-1,-1)
    return (a,b,c,d,e)

编辑1:顺便说一句，这不是作业，您可以查看我的其他问题并自己验证。谢谢..

Answer 1

有一个 O(n^3) 的解决方案，灵感来自 MRAB 的评论。

首先，将列表 1 中的每个值与列表 2 中的每个值组合起来，并将其存储在一个集合中。调用结果集 1and2，它有 n^2 个值。

接下来，将集合1and2与列表3合并。调用结果集1and2and3，它有n^3个值，需要n^3步构造。

接下来，合并列表 4 和 5。调用结果集 4 和 5，它有 n^2 个值。

最后，检查集合 4 和 5 中的任何值是否等于集合 1 和 2 和 3 中的值的倒数。这一步需要 n^2 步。

此方法使用 O(n^3) 空间和 O(n^3) 时间。

正如 Karoly Horvath 指出的那样，您实际上不需要存储集合 1 和 2 和 3，您可以在最后一步中从集合 1 和 2 动态构建它。这种方法仅使用 O(n^2) 空间，但仍需要 O(n^3) 时间。这是代码:

l1 = [1,2,3,4,5,10]
l2 = [1,2,3,4,5,11]
l3 = [1,2,3,4,5,12]
l4 = [1,2,3,4,5,13]
l5 = [1,2,3,4,5,-46]

def test():
    l1_2 = [a + b for a in l1 for b in l2]
    set4_5 = set([a + b for a in l4 for b in l5])
    return any([True for x in l1_2 for y in l3 if -(x + y) in set4_5])

print test()