arrays - 从两个数组中查找特定元素的总和

Question

你能帮我解决这个问题吗？：“让 A 和 B 是自然数的递增排序数组，K 是任意自然数。找到一个有效的算法来确定所有可能的索引对 (i,j)，使得 A[i]+B[j]= K. 证明算法的正确性并估计其复杂性。”

我应该只遍历第一个数组并对另一个数组进行二进制搜索吗？谢谢 ：）

Answer 1

不！

两个数组都是有序的，因此您可以执行以下操作：

• itA在开头放置一个迭代器A
• itB在末尾放置一个迭代器B
• 沿相反方向移动迭代器，*itA + *itB在每次迭代时进行测试。如果值等于K，则返回两个索引。如果该值小于K，则递增itA。否则，减量itB。

当你遍历两个数组时，你就在线性时间内完成了。

Answer 2

由于对于每个 A[i] 只能有一个 B[j]，因此您可以找到复杂度为 O(n+m) 的解。您可以相信，如果 (A[i1] B[j1]) 和 (A[i2] B[i2]) 都是正确的对，并且 i1 小于 i2，则 j1 必须大于 j2。希望这可以帮助。

Answer 3

我不知道它是否有帮助，这只是一个想法。线性循环 A 和二进制搜索 B，但向后执行 A。通过能够在 A 中的每个步骤排除 B 的某些部分，这可能会为您提供更好的最佳情况。

如果你知道 A[i] 需要说 B[42] 来求解 K，你就会知道 A[i-1] 至少需要 B[43] 或更高。

编辑：我还想补充一点，如果 B 的元素比 A 少，请将其转过来并线性执行 B。

Answer 4

C++ 中的可能实现如下所示：

#include <iostream>
int main()
{
    int A[]={1,2,3,6,7,8,9};
    int B[]={0,2,4,5,6,7,8,12};

    int K=9;
    int sizeB=sizeof B/sizeof(int);
    int sizeA=sizeof A/sizeof(int);


    int i=0;
    int j=sizeB-1;
    while(i<sizeA && j>=0)
    {
        if ((A[i]+B[j])==K){
            std::cout << i<<","<<j<< std::endl;
            i++;
            j--;
        }
        else if((A[i]+B[j])<K){
            i++;
        }
        else{
            j--;
        }
    } 
    return 0;
}