Étant donné deux ensembles a et b .Trouver toutes les paires d'éléments (a1,b1) tels que a1 appartient à la série A et b1 appartient à la Matrice B dont la somme a1+b1 = k

Si vous avez une limite sur le nombre maximum possible (appelons le M), alors vous pouvez avoir une solution en O(M+n).

Booléen tableau de faux et marquez-le comme une véritable valeur pour l'élément de A. Ensuite, pour chaque élément b de B vérifier si le numéro d'élément de K-b est marqué comme vrai.

Vous pouvez l'améliorer si vous êtes en utilisant un hash-carte à la place d'un grand tableau. Mais je ne serais pas envisager que dans ce genre de questions de hachage de la carte est de la triche.

De toute façon, il serait de vous donner des O(n) pour l'insertion et puis O(n) pour les requêtes, O(n) au total.

EDIT :

Un cas où cela pourrait être utile.

• Vous avez non triés vecteurs de taille 10^6, afin de les trier et de faire le match est en O(n log n) avec n = 10^6.
• Vous avez besoin pour effectuer cette opération 10^6 fois (différents vecteurs), la complexité de O(n*n*log n).
• Valeur maximale est de 10^9.

À l'aide de mon idée de ne pas booléens mais entier (incrémenté à chaque exécution) vous donne une complexité de :

• "O(10^9)" pour créer le tableau (de même qu'à la complexité de l'espace)
• O(n) à chaque exécution, donc O(n*n) pour le total.

Vous utilisez plus d'espace, mais vous avez l'augmentation de la vitesse par un facteur log(n) ~=20 dans ce cas !

Je voudrais créer une table de hachage contenant les éléments d'un tableau, puis effectuer une itération à l'autre de la matrice de recherche k - a(n), la génération d'un élément de sortie si la recherche a réussi. Cela implique l'utilisation de O(n) l'espace et le temps.

En C#, il pourrait ressembler à ceci:

var bSet = new HashSet(B);
var results = from a in A
              let b = k - a
              where bSet.Contains(b)
              select new { a, b };

J'ai utilisé le C++ et il semblait me donner le résultat souhaité. L'espoir c'est ce que vous cherchez.

using namespace std;
using data=std::pair<int,int>;
void search_pairs(std::vector<int>& A, std::vector<int>& B, const int total, std::vector<data>& output){
std::sort(A.begin(),A.end(),[](const int i,const int j)->bool{return (i<j);});
std::sort(B.begin(),B.end(),[](const int a,const int b)->bool{return (a<b);});
std::vector<int>* minV(nullptr);
std::vector<int>* maxV(nullptr);
if(A.size()>B.size()) {minV=&B;maxV=&A;}
else {minV=&A;maxV=&B;}
for(auto&& itr:(*minV) ){
auto remain(total-itr);
if (std::binary_search (maxV->begin(), maxV->end(), remain)){
data d{itr,remain};
if (minV==&B) std::swap(d.first,d.second);
output.push_back(d);
}
}
if (minV==&B) std::reverse(output.begin(),output.end());  
}
int main() {
size_t nb(0);
scanf("%lu",&nb);
for (size_t i=0;i<nb;++i){
size_t a,b(0);
int total(0);
scanf("%lu %lu %d",&a,&b,&total);
std::vector<int> A,B;
for (size_t i=0;i<a;++i){
int aux;
scanf("%d",&aux);
A.push_back(aux);
} 
for (size_t i=0;i<b;++i){
int aux;
scanf("%d",&aux);
B.push_back(aux);
} 
std::vector<data> output;
search_pairs(A, B, total, output);
auto itr=std::begin(output);
if (itr==std::end(output)) printf("-1"); 
while (itr!=std::end(output)){
printf("%d %d",(*itr).first, (*itr).second);
if (++itr!=std::end(output)) printf(", ");
}
printf("\n");
}
//code
return 0;
}