Problème à deux sommes » sur LeetCode

Description du problème
Étant donné un tableau de nombres entiers et une cible entière, renvoie les indices des deux nombres qui totalisent la cible.

Signature de fonction Go :
func twoSum(nums []int, cible int) []int
Exemple 1 :
Entrée : nums = [2,7,11,15], cible = 9
Sortie : [0,1]
Explication : Parce que nums[0] nums[1] == 9, nous renvoyons [0, 1].
Exemple 2 :

Entrée : nums = [3,2,4], cible = 6
Sortie : [1,2]
Exemple 3 :

nput : nums = [3,3], cible = 6
Sortie : [0,1]
Solution 1 : Approche par force brute

Solution 1 : Approche par force brute (boucles imbriquées)
Dans cette approche, vous vérifiez chaque paire d’éléments pour voir s’ils correspondent à l’objectif. Cela implique de parcourir le tableau avec deux boucles imbriquées.

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
}

Analyse de complexité

Solution 2 : Table de hachage à deux passes
Cette solution améliore l'approche par force brute en utilisant une carte de hachage pour stocker la valeur et l'index de chaque élément lors du premier passage. Lors de la deuxième passe, vous vérifiez si le complément (c'est-à-dire cible - num) existe dans la carte de hachage.

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
}

Solution 3 : Table de hachage en un seul passage (solution optimale)

• Cette approche combine à la fois l'insertion et la recherche en un seul passage. Lorsque vous parcourez le tableau, vous :

• Vérifiez si le complément (c'est-à-dire cible - num) existe dans la carte de hachage.

• Si le complément est trouvé, renvoie les indices.

• Sinon, ajoutez l'élément actuel et son index à la carte de hachage pour les recherches futures.
  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
}

Analyse de complexité

• Complexité temporelle : ?(?)

  • Un seul passage à travers le tableau est requis, ce qui approche linéaire en complexité temporelle.

• Complexité spatiale :o(n)

  • La carte de hachage stocke chaque élément et son index.

Avantages et inconvénients
Avantages : L'approche la plus efficace pour la complexité temporelle, avec une implémentation propre et compacte.
Inconvénients : Aucun, car il atteint une complexité temporelle et spatiale optimale pour ce problème.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!