Algorithmus zur Entscheidung, ob a, b, c in einem Array existieren, so dass a + b + c = z?

Question

ein wenig stecken fest, einen effizienten Algorithmus für das folgende Problem zu finden. Der Algo muss entscheiden, ob es 3 Elemente a, b und c in einem Array gibt, so dass a + b + c gleich einer gegebenen Zahl z ist.

Der naive Weg wäre natürlich, die Kombinationen auszuprobieren, aber asymptotisch wäre die benötigte Zeit zu groß.

Zum Finden von a und b in einem Array, so dass die Summe ist z viel einfacher. Sortieren Sie das angegebene Array in aufsteigender Reihenfolge und prüfen Sie jedes Element auf Vorhandensein von z-a. Aber ich bin nicht sicher, wie ich es in das 3-Element-Problem implementieren würde und welche Zeit benötigt würde.

Jede Hilfe wird sehr geschätzt!

Bearbeiten: a, b, c und z sind ganze Zahlen.

Answer 1

Der Ansatz ist dem Finden von a und b mit der Summe z sehr ähnlich.

Sortieren Sie zuerst das Array. Und dann fix eine an Position i und prüfen Sie, ob Sie Summe haben z-a in den Grenzen i + 1 to n

Da haben Sie einen O(n) Algorithmus zu überprüfen, ob eine Summe z existieren mit a und b. Wir erweitern es nur, um a zu reparieren und zu prüfen, ob zwei andere Variablen verwendet werden können, um die Summe zu erzeugen.

Von here

// returns true if there is triplet with sum equal 
// to 'sum' present in A[]. Also, prints the triplet 
bool find3Numbers(int A[], int arr_size, int sum) 
{ 
    int l, r; 

    /* Sort the elements */ 
    sort(A, A+arr_size); 

    /* Now fix the first element one by one and find the 
     other two elements */ 
    for (int i=0; i<arr_size-2; i++) 
    { 

     // To find the other two elements, start two index 
     // variables from two corners of the array and move 
     // them toward each other 
     l = i + 1; // index of the first element in the 
        // remaining elements 
     r = arr_size-1; // index of the last element 
     while (l < r) 
     { 
      if(A[i] + A[l] + A[r] == sum) 
      { 
       printf("Triplet is %d, %d, %d", A[i], 
             A[l], A[r]); 
       return true; 
      } 
      else if (A[i] + A[l] + A[r] < sum) 
       l++; 
      else // A[i] + A[l] + A[r] > sum 
       r--; 
     } 
    } 

    // If we reach here, then no triplet was found 
    return false; 
} 

Answer 2

Ich denke, ich hätte einen kurzen Kommentar als Antwort schreiben sollen, aber ich habe nicht genug Ruf dafür ... Also hier geht nichts!

---

Der beste Algorithmus ich jetzt kommen kann, ist O (n^2), diesen Algorithmus zu erklären, besser wir mit der a + b = z in O (n) Fall (oder O beginnen soll (nlgn) wenn es nicht sortiert wurde)

Zuerst iteriere {a} und finde {b} so, dass a + b = z. Naiv, wenn Sie alle b iterieren, würde dies O (n) pro {a} kosten, was zu einer O (n^2) -Lösung führt. Wenn Sie jedoch {a} zunehmend iterieren, muss der Wert von {b} streng abnehmen. Wir können den Gebrauch dieser Information machen die Zeitkomplexität wie in diesem Code zu reduzieren:

for a = first element, b = last element; a != last; a = next a 
while ((b != first element) and (a + b > z)) 
     b = previous elemnet of b 
if a + b == z 
     return true 

Beachten Sie, dass {b} geht nur durch die ganze Liste einmal im gesamten Schleife, so hat es eine Komplexität von fortgeführten Anschaffungs O (n) .

---

Jetzt können wir dieses Prinzip wieder auf das ursprüngliche Problem anwenden, wir durch laufen könnte {a}, und wenden Sie diese O (n) Algorithmus {b, c} finden {za}, die Gesamtkomplexität ist O (n * n = n^2).

Hoffentlich gibt es eine Lösung mit einer geringeren Komplexität, ich denke nicht, dass O (n^2) beeindruckend ist, aber ich kann mir einfach keinen besseren vorstellen.