在 O[n^2] 处找到所有给出结果 A[i]+B[j]=C[k] 和 3 个数组的组合

Question

有3个数组，每个数组的大小为N。找到仅在 O[n^2].

时给出 A[i]+B[j]=C[k] 的组合

Answer 1

更新：问题后来被修改为专门询问 Java 中的实现。 Python 中的算法和解释仍然有效，但我还在下面添加了 Java 实现。

使用hashmap（或一组）来测试时间复杂度O(1)（平均）在C中是否存在。然后你需要做的就是迭代所有对 (a,b) | a <- A, b <- B，总时间复杂度为 O(n^2).

例如，在 Python 中，您可以这样做：

c = set(C)
for a in A:
    for b in B:
        if a + b in c:
            print a, b, a + b

快速测试：

>>> A = [1,2,3]
>>> B = [3,4,5]
>>> C = [1,4,7]
>>> c = set(C)
>>> for a in A:
...     for b in B:
...         if a + b in c:
...             print a, b, a + b
... 
1 3 4
2 5 7
3 4 7

或者，具有列表理解的较短版本：

>>> c = set(C)
>>> [(a,b,a+b) for a in A for b in B if a+b in c]
[(1, 3, 4), (2, 5, 7), (3, 4, 7)]

Java的实现本质上是一样的。关键观察是使用 java.util.HashSet 检查总和 A[i]+B[j] 是否存在于数组 C:

中

import java.util.HashSet;

class Pairs {
    public static void main(String[] args) {
        Integer[] A = new Integer[]{1,2,3};
        Integer[] B = new Integer[]{3,4,5};
        Integer[] C = new Integer[]{1,4,7};

        HashSet<Integer> c = new HashSet<Integer>();
        for (int i = 0; i < C.length; i++) {
            c.add(C[i]);
        }

        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B.length; j++) {
                if (c.contains(A[i] + B[j])) {
                    System.out.format("%d %d %d%n", A[i], B[j], A[i]+B[j]);
                }
            }
        }
    }
}

Answer 2

有一个更简单的问题：给定两个数组和一个数字，从给出 sum=number 的数组中找到所有组合。它可以在 O(n) 中解决。

我们可以使用它的解决方案作为较大解决方案的一部分：

（我假设所有元素都不同 - 它稍微简化了事情）

sort(A)
sort(B)
sort(C)
for(int indexC=0;indexC<N;++indexC)
    int indexA=0
    int indexB=N-1
    while(indexA<0)
        //find all combinations in A,B with sum=C[indexC]
        int sum=A[indexA]+B[indexB]
        if(sum==C[indexC])
            OutputCombination(indexA,indexB,indexC)
        if(sum<C[indexC])
            ++indexA
        else if(sum>C[indexC])
            --indexB
        else
            ++indexA
            --indexB

在 O[n^2] 处找到所有给出结果 A[i]+B[j]=C[k] 和 3 个数组的组合

Find all combinations that gives the result A[i]+B[j]=C[k] with 3 arrays at O[n^2]

java

arrays

algorithm

combinations

equation