棘手的链表问题

Question

给出三个列表:A,B和C,每个长度为n.如果任何3个三个数字(每个列表1个),总和为零返回true.我想用o(n)复杂度来解决这个问题.我已经对列表进行了排序,我可以想到创建一个总和为2的哈希映射链接列表或比较3个列表[o(n*n*n)].建议一些方法来即兴发挥方法来降低复杂性......我想不出任何......谢谢

Answer 1

列表是排序的,对吗？在O(n)时间内从C构建排序数组C'.

对于每个的Ñ ²对X,ÿ在甲 × 乙,检查是否- (X + Ý)是在C"与二进制搜索.总的时间复杂度为O(ñ ²LG ñ),空间复杂度为O(ñ).

建立一个哈希表出来ç带来的时间复杂度进一步下降到O(ñ ²),在O(1)哈希表信仰的代价.

Answer 2

我不认为它是可能的o(n²)(即真的比它好n²),但它可以在O(n²)(即...... n²)中完成,如下所示:

首先,反向列表B获取B'(需要O(n)时间),一个列表,其项目按降序排序.首先,我们考虑在列表中找到两个元素A并将B'其与任何给定数字求和的问题:

我们可以像下面这样做(Python代码):

def getIndicesFromTwoArrays(A,B,t):
    a,b=0,0
    while(A[a]+B[b]!=t):
        b=b+1
        if b==len(B):
            return (-1,-1)
        if A[a]+B[b]<t:
            a=a+1
            b=b-1
            if a==len(A):
                return (-1,-1)
    return (a,b)

上面的运行时间是O(n).所需的额外空间是O(1)因为我们只需要存储两个指针.请注意,上述内容可以轻松转换,以便与双向链表一起使用.

然后,总的来说我们只需要做以下事情:

def test(A,B,C):
    B.reverse()
    for c in C:
        if getIndicesFromTwoArrays(A, B, c) != (-1,-1):
            return True
    return False

这导致运行时间O(n²)和额外空间O(1).