LeetCode: TwoSum-Problem

Das TwoSum-Problem ist eine klassische Codierungsherausforderung, die Ihre Problemlösungs- und Algorithmenfähigkeiten auf die Probe stellt.

In diesem Beitrag schauen wir uns zunächst eine unkomplizierte Lösung an, die leicht zu verstehen ist. Anschließend optimieren wir es Schritt für Schritt, um seine Effizienz zu verbessern. Ganz gleich, ob Sie neu im Umgang mit Algorithmen sind oder sich auf Vorstellungsgespräche vorbereiten, dieser Leitfaden hilft Ihnen, das Problem zu meistern. Fangen wir an!

let inputArray = [2, 7, 11, 15]
let target = 9
console.log(twoSum(inputArray, target)) // Output: [0, 1]

Sehen wir uns die Eingabe und Ausgabe an, die die Funktion verarbeiten soll.

Bei gegebenem Array [2,7,11,15] und einem Zielwert von 9 lautet die Ausgabe [0,1].

Dies liegt daran, dass sich die Werte bei den Indizes 0 und 1 zu 9 addieren, was dem Ziel entspricht.

function twoSum(nums, target) {
  const hashMap = {}
}

Wir werden uns eine Lösung überlegen, bei der wir eine HashMap erstellen, um die Zahl im Array als Schlüssel und ihren Index als Wert zu speichern.

function twoSum(nums, target) {
  const hashMap = {}

  for (let i = 0; i < nums.length; i++) {
    hashMap[nums[i]] = i
  }
}

Dies ist der erste Teil der Lösung: Vorbereiten der HashMap.

In der nächsten Schleife prüfen wir, ob die HashMap das Komplement des Ziels minus der aktuellen Zahl im Array enthält.

function twoSum(nums, target) {
  const hashMap = {}

  for (let i = 0; i < nums.length; i++) {
    hashMap[nums[i]] = i
  }

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]

    if (hashMap[complement] !== undefined && hashMap[complement] !== i) {
      return [i, hashMap[complement]]
    }
  }
}

Wenn das Komplement in der HashMap gefunden wird, können wir auf seinen Index zugreifen, da wir seinen Wert haben.

Dann können wir ein Array zurückgeben, das seinen Wert (den Index des Komplements) zusammen mit i enthält, das die aktuelle Iteration darstellt.

In dieser Lösung sehen wir, dass wir zwei separate Schleifen erstellen. Wir können sie in einer einzigen Schleife kombinieren und so eine Iteration sparen.

function twoSum(nums, target) {
  const hashMap = {}

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]

    if (hashMap[complement] !== undefined && hashMap[complement] !== i) {
      return [i, hashMap[complement]]
    }
    hashMap[nums[i]] = i
  }
}

Wir haben die Bedingung zur besseren Übersichtlichkeit verfeinert und den folgenden Code erhalten:

function twoSum(nums, target) {
  const hashMap = {}

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]

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

let inputArray = [2, 7, 11, 15]
let target = 9
console.log(twoSum(inputArray, target)) // Output: [0, 1]

Das obige ist der detaillierte Inhalt vonLeetCode: TwoSum-Problem. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!