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 < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      console.log(` i is ${nums[i]} and k is ${nums[j]}`)
      // lets check if we add the 2 numbers if it equals target
      if (target === nums[i] + nums[j]) {
        return [i, j]
      }
    }
  }
};

const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(nums, target));

Ansatz 1 Komplexität

Zeitkomplexität ist O(n²)

1. Verschachtelte Schleifen, die jedes Zahlenpaar prüfen
2. Überprüft jede mögliche Kombination
3. Wird bei großen Arrays sehr langsam

Raumkomplexität ist O(1)
1.Wir haben keine neue Datenstruktur erstellt

Ansatz 2: Effizienter und was wir wollen.

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

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

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

const twoSumOptimizedRegularObject = (nums, target) => {
  const objectStuff = {}

  // write a for loop, to go through the arr
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i] 

    if (complement in objectStuff) {
      return [objectStuff[complement],i]
    }
    objectStuff[nums[i]] = i 
  }
}

const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSumOptimizedRegularObject(nums, target));

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.

const twoSumOptimized = (nums, target) => {
  const mapOfStuff = new Map()

  // write a for loop, to go through the arr
  for (let i = 0; i < nums.length; i++) {
    let complement = target - nums[i]

    if (mapOfStuff.has(complement)) {
      return [mapOfStuff.get(complement), i]
    }
    mapOfStuff.set(nums[i], i)
  }

}

const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSumOptimized(nums, target));

Ansatz 2 Komplexität

Zeitkomplexität ist O(n)

1. Einzelner Durchgang durch das Array
2. Hash-Map bietet O(1)-Suche
3. Die Gesamtzeit skaliert linear mit der Array-Größe

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

Vorbehalte

1. Leeres Array
2. Es gibt keine Lösung
3. Mehrfachlösung möglich. Fragen Sie in diesem Fall, ob Sie nach der ersten Iteration zurückkehren.

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!