Algorithmus zum Zählen der Anzahl von Paaren, deren Summe im Array existiert

Question

Gegeben eine Reihe von N ganzen Zahlen. Wie kann ich die Anzahl der Paare zählen, deren Summe im Array existiert?

z. int a[] = {1, 3, 4, 6, 7}. Hier gibt es drei solche Paare: (1 + 3) = 4, (3 + 4) = 7, (1 + 6) = 7.

Es gibt keine doppelten Nummern im angegebenen Array und das Array ist nicht sortiert Auch das Array kann geändert werden, es ist nicht notwendig, das Array zu verwalten.

Ich habe die folgenden zwei Codes versucht, aber ich möchte die Komplexität meines Codes auf weniger als O (n^2) reduzieren.

Versuchen 1: (Komplexität ist O (n^3))

#include<iostream> 
#include<vector> 
#include<algorithm> 
using namespace std; 
main(){ 
    int i,input,j,n,ans=0,sum; 
    cin>>n; 
    vector<int> vec; 
    for(i=0;i<n;i++){ 
     cin>>input; 
     vec.push_back(input); 
    } 
    for(i=0;i<n;i++){ 
     for(j=i+1;j<n;j++){ 
      sum=vec[i]+vec[j]; 
      if(find(vec.begin(),vec.end(),sum)!= vec.end()){ 
       ans++; 
      } 
     } 
    } 
    cout<<ans; 
} 

Answer 1

Ich bin mir nicht sicher, ob dies die Komplexität reduzieren helfen, aber ich denke, es ist einfacher, ist auf diese Weise, da Sie nicht ausdrücklich erklären, alle Variablen in der Funktion, die Sie verwenden, das Speichern der Erinnerung und Zeit:

#include<iostream> 
#include<vector> 
#include<algorithm> 
using namespace std; 
bool checkForEveryElement(vector<int> vec,int sum) 
{ 
    for(int i=0; i<vec.size(); i++) 
    { 
     for(int j=i+1; j<vec.size(); j++) 
      if(vec[i] + vec[j] == sum) 
      return 1; 
    }  
    return 0; 
} 
void main(){ 
    int i,input,j,n,ans=0,sum; 
    cin>>n; 
    vector<int> vec; 
    for(i=0;i<n;i++){ 
     cin>>input; 
     vec.push_back(input); 
    } 
    sort(vec.begin(),vec.end()); 
    for(i=0;i<n;i++) 
     if(checkForEveryElement(vec,vec[i])){ 
      ans++; 
     } 
    cout<<ans; 
} 

Answer 2

Sie können es durch Arrays oder Vektoren, so dass Sie als bubble-Sortieralgorithmus laufen kann; Also beginnt die erste Schleife (äußere) von Element 0 bis zum Ende und die innere Schleife beginnt mit dem äußeren Schleifenindex + 1, um zu vermeiden, dass das Element mit sich selbst summiert wird. Und jede innere Schleife berechnet die Summe von Element i + Element i + 1. Speichern der Summe in einer temporären Variablen. Schließlich wird eine innerste Schleife beginnt von i + 2 Solange i mit j summiert (i + 1) und das Ergebnis aus dem dritten Element beginnt:

int a[] = {1, 3, 4, 6, 7}; 

for(int i(0); i < 5; i++){ 
    for(int j(i + 1); j < 5; j++){ 
     int sum = a[i] + a[j]; 
     for(int k(j + 1); k < 5; k++){ 
      if (sum == a[k]) 
       std::cout << "(" << a[i] << ", " << a[j] << "): " << sum << std::endl; 
     } 
    } 
} 

* wünsche ich dies Ihnen helfen wird, in der verstrichenen Zeit reduziert .