[BOJ-3273] Résolvons le problème de la somme de deux nombres de deux manières (Hash, Two Pointers) avec Go

Problème

Accéder à BOJ-3273

n nombres entiers positifs distincts a1, a2, ..., an composent une séquence. La valeur de ai est un entier naturel qui est supérieur ou égal à 1 et inférieur ou égal à 1000000.  

Quand on nous donne un nombre naturel x, écrivons un programme pour compter le nombre de paires (ai, aj) telles que ai + aj = x (1 ≤ i < j ≤ n).

Le problème consiste à déterminer si une somme correspond au nombre désigné x dans le tableau donné comme ci-dessus.

Pour des raisons de commodité, nous appellerons x target ci-après.

1. Résoudre avec une double boucle

Lorsqu’on a d’abord reçu le problème, on pourrait penser qu’on peut le résoudre en parcourant le tableau deux fois pour trouver.

L’algorithme clé est le suivant.

package main

import "fmt"

func main() {
	// ... code d'initialisation

	count := 0
	for i, num := range arr {
		for j, num2 := range arr {
			if i >= j {
				continue
			}
			if num+num2 == target {
				count++
			}
		}
	}
	fmt.Println(count)
}

La méthode consiste simplement à effectuer une double boucle pour trouver sans finesse.

Cependant, avec la contrainte de n, 1 ≤ n ≤ 100000,si nous utilisons cette méthode, dans le pire des cas, cela donnera un O(n^2).

Si nous avons une entrée maximale de 100,000 * 100,000 = 10,000,000,000, le nombre de comparaisons nécessaires est gigantesque.

Naturellement, si nous exécutons réellement ce code, nous obtiendrons un dépassement de temps.

Nous devons réfléchir à une réponse plus rapide et plus efficace.

2. Résoudre avec les deux pointeurs

Il existe une méthode appelée “deux pointeurs” où deux pointeurs se déplacent sur un seul tableau pour trouver la solution.

Dans ce cas particulier, si le tableau est trié, le problème peut être facilement résolu avec les deux pointeurs.

En prenant un tableau trié comme référence, start commence à 0 et end commence à n-1.

Supposons qu’il y ait une entrée comme celle-ci:

arr = [5, 1, 3, 2, 4]
target = 5

Une fois trié, cela ressemblera à ceci.

Maintenant, commençons à chercher à start = 0 et end = 4.

Étape 1

count = 0

La somme des deux nombres est 6.

C’est supérieur à 5, donc nous diminuons end.

Étape 2

count = 0

Maintenant, la somme des deux est 5.

La somme correspond à target, donc nous augmentons count.

Comme le tableau comporte des valeurs distinctes, nous déplaçons les deux pointeurs. start passe à 1, end à 2.

Étape 3

count = 1

Même en déplaçant les pointeurs, la somme est toujours 5.

Ceci correspond à target, donc nous augmentons count.

En déplaçant, start devient 2, end devient 1.

Maintenant, start est supérieur à end, donc nous arrêtons.

Complexité temporelle

La complexité temporelle de cette méthode avec deux pointeurs est O(n), mais le tri nécessite O(n*Log(n)), donc la complexité finale est O(n*Log(n)).

Code final

Le code final est le suivant.

package main

import (
	"bufio"
	"fmt"
	"log"
	"os"
	"sort"
)

// https://www.acmicpc.net/problem/3273 - Somme de deux nombres

func main() {
	writer := bufio.NewWriter(os.Stdout)
	reader := bufio.NewReader(os.Stdin)
	defer writer.Flush()

	var n int
	if _, err := fmt.Fscanln(reader, &n); err != nil {
		log.Fatal(err)
	}

	arr := make([]int, n)
	for i := 0; i < n; i++ {
		if _, err := fmt.Fscan(reader, &arr[i]); err != nil {
			log.Fatal(err)
		}
	}
	if _, err := fmt.Fscanln(reader); err != nil {
		log.Fatal(err)
	}
	var target int
	if _, err := fmt.Fscanln(reader, &target); err != nil {
		log.Fatal(err)
	}

	sort.Ints(arr)

	count := 0
	start, end := 0, len(arr)-1
	for start < end {
		sum := arr[start] + arr[end]
		if sum == target {
			count++
			start++
			end--
		}
		if sum > target {
			end--
		}
		if sum < target {
			start++
		}
	}

	fmt.Println(count)
}

3. Implémentation avec un Hash

Le problème peut également être résolu en utilisant un hash.

Nous utiliserons le complément et le hashmap.

Par exemple, le complément de 4 pour 10 est 10 - 4 = 6.

Voyons la logique avec le même tableau qu’auparavant:

Nous n’avons pas besoin de trier avec un hash, et nous ne devons parcourir la boucle qu’une seule fois.

Étape 1

count = 0

Tableau

Hashmap

D’abord, avec i ayant une valeur de 5. Vérifiez si le complément, qui est 0, est dans le hashmap.

Ce n’est pas le cas, donc le compteur reste inchangé et nous ajoutons la valeur actuelle au hashmap.

Étape 2

count = 0

Tableau

Hashmap

Ensuite, pour i=1, la valeur est 1, donc nous cherchons le complément, qui est 4, dans le hashmap.

Comme il n’existe pas de clé 4 dans le hashmap, le compteur reste inchangé et nous ajoutons la valeur actuelle au hashmap.

Étape 3

count = 0

Tableau

Hashmap

Puis, pour i=2, la valeur est 3, et le complément, qui est 2, n’est pas dans le hashmap. Nous ajoutons simplement la valeur actuelle.

Étape 4

count = 0

Tableau

Hashmap

Pour i=3, la valeur est 2, donc cherchons le complément, qui est 3, dans le hashmap.
Il existe une clé 3, donc nous augmentons le compteur et ajoutons la valeur actuelle au hashmap.

Étape 5

count = 1

Tableau

Hashmap

Pour i=4, la valeur est 4. Donc, cherchons son complément, qui est 1, dans le hashmap. Étant donné que la clé 1 existe, nous augmentons le compteur de 1 et ajoutons la valeur actuelle.

Résultat

count = 2 Tableau

Hashmap

Comme i atteint 5, l’algorithme s’arrête, et le nombre final de paires est de 2.

Complexité temporelle

L’utilisation du hash ne nécessite pas de tri, et on n’exécute la boucle qu’une seule fois. Cela donne une complexité temporelle de O(n).
Il faut cependant noter que la consommation de mémoire pourrait augmenter considérablement en fonction de l’entrée.

Code final

Le code correspondant en Go est le suivant.

package main

import (
	"bufio"
	"fmt"
	"log"
	"os"
)

// https://www.acmicpc.net/problem/3273 - Somme de deux nombres

func main() {
	writer := bufio.NewWriter(os.Stdout)
	reader := bufio.NewReader(os.Stdin)
	defer writer.Flush()

	var n int
	if _, err := fmt.Fscanln(reader, &n); err != nil {
		log.Fatal(err)
	}

	arr := make([]int, n)
	for i := 0; i < n; i++ {
		if _, err := fmt.Fscan(reader, &arr[i]); err != nil {
			log.Fatal(err)
		}
	}
	if _, err := fmt.Fscanln(reader); err != nil {
		log.Fatal(err)
	}
	var target int
	if _, err := fmt.Fscanln(reader, &target); err != nil {
		log.Fatal(err)
	}

	count := 0
	idxMap := make(map[int]int)
	for i, num := range arr {
		// Cherchez le complément pour num
		if _, ok := idxMap[target-num]; ok {
			count++
		}
		// Ajoutez la valeur actuelle au hashmap
		idxMap[num] = i
	}

	if _, err := fmt.Fprintln(writer, count); err != nil {
		log.Fatal(err)
	}
}

Conclusion

Nous avons réussi à résoudre le problème en utilisant des techniques de Hash et de deux pointeurs.

J’ai revu et résumé cela pour me préparer à aborder des problèmes similaires lors des tests de codage.

Je me considère un peu idiot d’avoir utilisé la première méthode.🤣

(Après avoir résolu un problème d’algorithme depuis longtemps, j’ai perdu mon sens, donc j’ai pensé trop simplement.)

J’ai également essayé de le résoudre en utilisant la recherche binaire, mais en fin de compte, en réfléchissant davantage, j’ai pu trouver une bonne méthode.

(Pourquoi n’arrive-t-on pas à penser à de telles méthodes lors des examens ? ㅠㅠ)

Il semble que je devrais souvent résoudre ce type de problème et prendre le temps de le résumer afin que cela m’aide également lors des examens.

Allez, courage !