Algorithmen und Datenstrukturen · Senior · Frage 64 von 75
Wie findet man in einem Array mit Duplikaten alle Paare mit gegebener Summe, ohne doppelt zu zählen?
- 1Sortieren und für jedes Element binär suchen, jeden Treffer addieren
- 2Werte in einer Map zählen und Zählungen paaren, mit Sonderfall x = target - x
- 3Die Werte in ein
Setlegen und einmal darüber iterieren
Antwort zeigen
Richtige Antwort: Werte in einer Map zählen und Zählungen paaren, mit Sonderfall x = target - x
Erklärung
Paare jedes verschiedene x mit count[target - x]; ist x gleich seinem Komplement, nutze c × (c - 1) / 2. Verarbeite jedes Wertepaar einmal (x < Komplement). Ein Set verliert die Zählungen.