Zwei-Summen-Problem in Javascript

Allgemeine Idee

Das Zweisummenproblem ist ein klassisches algorithmisches Problem. Sie werden aufgefordert, zwei Zahlen in einem Array zu finden, die sich zu einem bestimmten *Ziel * addieren, das bereitgestellt wird, und dann ihre Indizes aus dem angegebenen Array zurückzugeben.

Problemstellung

Geben Sie bei einem gegebenen Array von Ganzzahlen und einem Ganzzahlziel die Indizes der beiden Zahlen so zurück, dass sie sich zum Ziel addieren. Jede Eingabe hat genau eine Lösung und Sie dürfen dasselbe Element nicht zweimal verwenden.

Eingabe: Nums = [2, 7, 11, 15], Ziel = 9
Ausgabe: [0, 1]
Erläuterung: nums[0] nums[1] = 2 7 = 9

Ansatz 1 Brutale Gewalt

Der erste Ansatz für jedes Problem könnte einfach darin bestehen, etwas zu erledigen und das konzeptionell am einfachsten.

Durchlaufen Sie das Array mit zwei Schleifen und überprüfen Sie alle Zahlenpaare.

const twoSum = (nums, target) => {
  for(let i = 0; i 



<h3>
  
  
  Ansatz 1 Komplexität
</h3>

<p><strong>Zeitkomplexität</strong> ist <em>O(n²)</em></p>

<ol>
<li>Verschachtelte Schleifen, die jedes Zahlenpaar prüfen</li>
<li>Überprüft jede mögliche Kombination</li>
<li>Wird bei großen Arrays sehr langsam</li>
</ol>

<p><strong>Raumkomplexität</strong> ist <em>O(1)</em><br>
1.Wir haben keine neue Datenstruktur erstellt</p>
<h2>
  
  
  Ansatz 2: Effizienter und was wir wollen.
</h2>

<p>Wir werden eine Hash-Map verwenden, um dieses Problem zu lösen. Lassen Sie uns diesen Algorithmus etwas erklären</p>

<ol>
<li>Wir verwenden eine Hash-Map (Objekt in JavaScript), um Zahlen zu speichern, die wir gesehen haben</li>
<li>Für jede Zahl berechnen wir ihr Komplement (Ziel – aktuelle Zahl)</li>
<li>Wir prüfen, ob die Ergänzung in unserer Karte vorhanden ist</li>
<li>Wenn ja, haben wir unsere beiden Zahlen gefunden und geben ihre Indizes zurück</li>
<li>Wenn nicht, fügen wir die aktuelle Nummer zur Karte hinzu</li>
</ol>

<p>Die erste Lösung könnte also darin bestehen, das reguläre JS-Objekt zu verwenden und unsere HashMap auf diese Weise zu erstellen<br>
</p>

<pre class="brush:php;toolbar:false">const twoSumOptimizedRegularObject = (nums, target) => {
  const objectStuff = {}

  // write a for loop, to go through the arr
  for (let i = 0; i 



<p>Die zweite Lösung ist tatsächlich die Verwendung der Kartendatenstruktur in JS. Dies ermöglicht strengere und robustere Implementierungen unter Verwendung eines Kartenobjekts (eingeführt in ES6) und wird oft bevorzugt. Eine Map bietet explizites Hash-Map-Verhalten und vermeidet einige Eigenheiten von JavaScript-Objekten, wie das Erben von Eigenschaften von Object.prototype.<br>
</p>

<pre class="brush:php;toolbar:false">const twoSumOptimized = (nums, target) => {
  const mapOfStuff = new Map()

  // write a for loop, to go through the arr
  for (let i = 0; i 



<h3>
  
  
  Ansatz 2 Komplexität
</h3>

<p><strong>Zeitkomplexität</strong> ist <em>O(n)</em></p>

<ol>
<li>Einzelner Durchgang durch das Array</li>
<li>Hash-Map bietet O(1)-Suche</li>
<li>Die Gesamtzeit skaliert linear mit der Array-Größe</li>
</ol>

<p><strong>Raumkomplexität</strong> ist O(n)<br>
Im schlimmsten Fall könnten wir fast alle Nummern speichern<br>
Kompromiss zwischen Zeit und Speichereffizienz</p>

<h2>
  
  
  Vorbehalte
</h2>

<ol>
<li>Leeres Array</li>
<li>Es gibt keine Lösung</li>
<li>Mehrfachlösung möglich. Fragen Sie in diesem Fall, ob Sie nach der ersten Iteration zurückkehren.</li>
</ol>


          

            
        

Das obige ist der detaillierte Inhalt vonZwei-Summen-Problem in Javascript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!