棘手的链表问题

Question

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

Answer 1

列表已排序，对吗？在 O(n) 时间内从 C 构建一个排序数组 C'。

对于 A × B 中的每一个 n² 对 x、y，使用二分查找检查 -(x + y) 是否在 C' 中。总时间复杂度为 O(n² lg n)，空间复杂度为 O(n)。

用C构建哈希表可以将时间复杂度进一步降低到O(n²)，但代价是对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)。

Answer 3

你不能用 O(n) 的复杂度来做到这一点，因为它是 NP 完全问题（除非 P=NP）。请查看有关子集和问题的 Wiki 页面以获取可能的解决方案。