„Zwei-Summen-Problem' auf LeetCode

Problembeschreibung
Geben Sie bei einem gegebenen Array aus ganzen Zahlen und einem ganzzahligen Ziel die Indizes der beiden Zahlen zurück, die sich zum Ziel addieren.

Go-Funktionssignatur:
func twoSum(nums []int, target int) []int
Beispiel 1:
Eingabe: Nums = [2,7,11,15], Ziel = 9
Ausgabe: [0,1]
Erläuterung: Da nums[0] nums[1] == 9 ist, geben wir [0, 1] zurück.
Beispiel 2:

Eingabe: nums = [3,2,4], Ziel = 6
Ausgabe: [1,2]
Beispiel 3:

nput: nums = [3,3], target = 6
Ausgabe: [0,1]
Lösung 1: Brute-Force-Ansatz

Lösung 1: Brute-Force-Ansatz (verschachtelte Schleifen)
Bei diesem Ansatz überprüfen Sie jedes Elementpaar, um zu sehen, ob es in der Summe das Ziel ergibt. Dies beinhaltet das Durchlaufen des Arrays mit zwei verschachtelten Schleifen.

Code

func twoSum(nums []int, target int) []int {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] + nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return nil
}

Komplexitätsanalyse

Lösung 2: Hash-Tabelle mit zwei Durchgängen
Diese Lösung verbessert den Brute-Force-Ansatz, indem sie eine Hash-Map verwendet, um den Wert und den Index jedes Elements im ersten Durchgang zu speichern. Im zweiten Durchgang prüfen Sie, ob das Komplement (d. h. Ziel – Zahl) in der Hash-Map vorhanden ist.

Code

func twoSum(nums []int, target int) []int {
    numMap := make(map[int]int)
    // First pass: populate the map with each element's index
    for i, num := range nums {
        numMap[num] = i
    }
    // Second pass: check for the complement
    for i, num := range nums {
        if j, ok := numMap[target - num]; ok && i != j {
            return []int{i, j}
        }
    }
    return nil
}

Lösung 3: One-Pass-Hash-Tabelle (optimale Lösung)

• Dieser Ansatz kombiniert sowohl das Einfügen als auch das Suchen in einem einzigen Durchgang. Während Sie das Array durchlaufen, geschieht Folgendes:

• Überprüfen Sie, ob das Komplement (d. h. Ziel – Zahl) in der Hash-Map vorhanden ist.

• Wenn das Komplement gefunden wird, geben Sie die Indizes zurück.

• Wenn nicht, fügen Sie das aktuelle Element und seinen Index zur Hash-Map für zukünftige Suchvorgänge hinzu.
  Code
  

func twoSum(nums []int, target int) []int {
    numMap := make(map[int]int)
    for i, num := range nums {
        if j, ok := numMap[target - num]; ok {
            return []int{j, i}
        }
        numMap[num] = i
    }
    return nil
}

Komplexitätsanalyse

• Zeitkomplexität: ?(?)

  • Daher ist nur ein Durchlauf durch das Array erforderlich Ansatz linear in der Zeitkomplexität.

• Raumkomplexität:o(n)

  • Die Hash-Map speichert jedes Element und seinen Index.

Vor- und Nachteile
Vorteile: Der effizienteste Ansatz für Zeitkomplexität, mit einer sauberen und kompakten Implementierung.
Nachteile: Keine, da die optimale zeitliche und räumliche Komplexität für dieses Problem erreicht wird.

Das obige ist der detaillierte Inhalt von„Zwei-Summen-Problem' auf LeetCode. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!