一组 3 个数字相等，其总和等于 T 形式 3 个未排序数组 ABC

Question

我们有三个数组A，B和C，未排序，每个数组有n个数字。我们想要找到一组三个数字 a、b 和 c，其中 a ε A、B ε B 和 C ε C，使得这些数字等于 T.（a + b + c = T）

请解决复杂度 O（n.logn） 和 O（n.logn²）（时间复杂度）

Answer 1

显而易见的方法就是蛮力。

for(i in a)
    for(j in b)
        for(k in c)
            if(i+j+k == key)
                //add triple to the result set

不过，这具有 O（n³） 的时间复杂度。如果我们对数组 c 进行排序，我们可以做得更好。

sort(c)
for(i in a)
    x = key-i
    for(j in b)
        x -= j
        if(c.binary_search(x) != -1) //assuming -1 means element doesn't exist
            //add i, j, and x, to the result set

这具有 O（n².log n） 的复杂度

更进一步的优化是对数组 b 和 c 进行排序。

sort(c)
sort(b)
for(i in a)
    x = key-i
    bi = 0
    ci = n-1
    while(ci >= 0 && bi < n)
        if(b[bi]+c[ci] == x)
            //add to result set
        else if(b[bi]+c[ci] > x)
            ci--
        else
            bi++        

这将在 O（n²） 中运行。

编辑：

O（n.log n） 溶液

sort(a)
sort(b)
sort(c)
ai = 0
bi = n-1
while(ai < n && bi >= 0)
    x = key-(a[ai]+b[bi])
    if(x < c[0])
        bi--
    else if(x > c[n-1])
        ai++
    else if(c.binary_search(x) != -1) //assuming -1 means element doesn't exist
        //add to result set

编辑：我意识到这个O（n.log n）算法是不正确的。它可能永远不会停止。尽管如此，我还是会将其留在帖子中，以防有人可以提出修复建议。

Answer 2

首先对 B 和 C 数组进行排序

B.sort()
C.sort()

现在我们将对 3Sum 算法进行一些修改，以搜索 B 和 C 中的值。我们将使用相同的技巧，但在两个不同的数组上，而不是一个数组

def Find_Sum(A, B, C, T):
    for a in A:
        bi = 0
        ci = len(C)
        while(bi < len(B) and ci >= 0):
            b = B[bi]
            c = C[ci]
            s = a + b + c
            if s == T:
                return (a, b, c)
            elif s > T:
                ci -= 1
            else:
                bi += 1
    return False

此算法为 O（n²）。

如维基百科页面所述，您可以通过计算 A+B 并将其与 C 进行比较来实现 O（n + nlogn）。我会让你为这个做研究。

Answer 3

O（n²） 算法：

1 - 使用合并排序，将数组合并为排序数组

2 - 现在通过一点修改来解决 3SUM 问题

 S = Mergesort(A,B,C);
 for i=0 to n-3 do
    a = S[i];
    k = i+1;
    l = n-1;
    while (k<l) do
       b = S[k];
       c = S[l];
       if (a+b+c == T) then
          output a, b, c;
          exit;
       else if (a+b+c > 0) then
          l = l - 1;
       else
          k = k + 1;
       end   
    end
 end
output "not found"//or return whatever you want!

当整数在 [-u， ...， u] 范围内时，3SUM 可以在 O（n + u.log u） 时间内求解，方法是将输入集 S 表示为位向量，使用快速傅里叶变换将所有成对和的集合 S+S 计算为离散卷积，最后将此集合与 -S 进行比较。