從兩個數組中找出特定元素的總和

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

我不知道是否有幫助，它只是一個想法。循環線性和二元搜索B，但是做A倒退。如果你知道A [1]需要說B [42]，以解決對K，你會這可能會給你一個更好的最好的情況下，能夠在A.

每一步排除B的某些部分知道A [i-1]至少需要B [43]或更高。

編輯：我還想補充一點，如果B具有較少的元素比A，扭轉它和做B線代替。

Answer 3

由於對於每個A [I]只能有一個B [j]時，就可以找到O（N + M）的複雜性的解決方案。如果（A [i1] B [j1]）和（A [i2] B [i2]）都是正確對，並且i1小於i2，則j1必須大於j2。希望這可以幫助。

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; 
}