[BOJ-3273] Lass uns das Problem der zwei Summen auf zwei Arten lösen (Hash, Two Pointer) Mit Go

Problem

BOJ-3273 Direktlink

n verschiedene positive Ganzzahlen a1, a2, ..., an. Die Werte ai sind natürliche Zahlen, die >= 1 und <= 1000000 sind.

Schreibe ein Programm, das die Anzahl der Paare (ai, aj) berechnet, die die Bedingung ai + aj = x (1 ≤ i < j ≤ n) erfüllen.

Es ist gefragt, ob die Summe aus dem gegebenen Array die vorgegebene Zahl x ergibt.

Zur Vereinfachung werde ich im Folgenden x als target bezeichnen.

1. Mit doppelter Schleife lösen

Als ich das Problem das erste Mal sah, dachte ich, dass ich einfach das Array zweimal durchlaufen könnte, um das Ergebnis zu finden.

Die Kernlogik sieht folgendermaßen aus:

package main

import "fmt"

func main() {
	// ... Initialisierungscode

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

Dies ist eine naive Methode, die das Array zweimal durchläuft.

Da die Einschränkung für n jedoch 1 ≤ n ≤ 100000 beträgt, würde diese Methode im schlechtesten Fall O(n^2) kosten.

Wenn die maximale Eingabe kommt, müssten 100.000 * 100.000 = 10.000.000.000 Vergleiche angestellt werden.

Ziemlich erwartungsgemäß führt das tatsächliche Ausführen dieses Codes zu einem Timeout.

Wir müssen also eine schnellere und effizientere Lösung finden.

2. Mit Two Pointers lösen

Es gibt eine Methode namens Two Pointers. Dabei bewegen sich zwei Zeiger über ein Array, um die Lösung zu finden.

In diesem Fall können wir das Problem mit dem Two Pointer Ansatz einfach lösen, wenn wir das Array sortieren.

Die beiden Pointer start und end beginnen mit start von 0 und end von n-1.

Nehmen wir beispielsweise folgende Eingabe:

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

Nach dem Sortieren sieht das Array folgendermaßen aus:

Jetzt schauen wir mit start auf 0 und end auf 4.

Stage 1

count = 0

Die Summe der beiden Zahlen beträgt 6.

Da diese größer als 5 ist, senken wir end.

Stage 2

count = 0

Nun beträgt die Summe der beiden Zahlen 5.

Da die Summe mit target übereinstimmt, erhöhen wir count.

Da das Array unterschiedliche Werte hat, bewegen wir beide Pointer. start wird auf 1 und end auf 2 gesetzt.

Stage 3

count = 1

Wenn wir die Pointer verschieben, beträgt die Summe wieder 5.

Da diese mit dem target übereinstimmt, erhöhen wir erneut count.

Beim Verschieben der Pointer wird start auf 2 und end auf 1 gesetzt.

Da nun start größer als end ist, beenden wir den Vorgang.

Zeitkomplexität

Die Zeitkomplexität dieser Logik beträgt O(n) dank der Two Pointers, aber durch das Sortieren benötigt man O(nLog(n)), sodass die finale Zeitkomplexität O(nLog(n)) beträgt.

Finale Code

Der finale Code sieht folgendermaßen aus:

package main

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

// https://www.acmicpc.net/problem/3273 - Zwei Summen

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. Mit Hash lösen

Man kann auch eine Hash-Methode verwenden, um das Problem zu lösen.

Hierbei wird ein Komplement und eine Hashmap verwendet.

Wenn wir zum Beispiel das Komplement von 4 zu 10 betrachten, ergibt das 10 - 4 = 6.

Werfen wir einen Blick auf die Logik mit demselben Array:

Bei Verwendung von Hash ist kein Sortieren erforderlich, und die Schleife muss nur einmal durchlaufen werden.

Stage 1

count = 0

Array

Hashmap

Zuerst ist der Wert an i 5. Wir prüfen, ob der Wert des Komplements 0 in der Hashmap vorhanden ist.

Wenn nicht, bleibt der Count gleich, und wir fügen den aktuellen Wert in die Hashmap ein.

Stage 2

count = 0

Array

Hashmap

Jetzt, bei i=1, ist der Wert 1, und wir suchen das Komplement 4 in der Hashmap.

Da der Schlüssel 4 nicht vorhanden ist, bleibt der Count gleich, und wir fügen den aktuellen Wert in die Hashmap ein.

Stage 3

count = 0

Array

Hashmap

Jetzt ist der Wert bei i=2, der 3 ergibt, und wir suchen das Komplement 2 in der Hashmap.

Da der Schlüssel 2 nicht vorhanden ist, bleibt der Count gleich und wir fügen den aktuellen Wert in die Hashmap ein.

Stage 4

count = 0 Array

Hashmap

Jetzt ist der Wert bei i=3, der 2 ergibt. Wir suchen nach dem Komplement 3 in der Hashmap.

Da der Schlüssel 3 vorhanden ist, erhöhen wir den Count und fügen dann den aktuellen Wert in die Hashmap ein.

Stage 5

count = 1

Array

Hashmap

Jetzt ist der Wert bei i=4, der 4 ergibt. Wir suchen nach dem Komplement 1 in der Hashmap.

Der Schlüssel 1 ist vorhanden, also erhöhen wir den Count und fügen dann den aktuellen Wert hinzu.

Ergebnis

count = 2 Array

Hashmap

i hat nun den Wert 5 erreicht, und wir beenden den Vorgang.

Der finale Count beträgt 2.

Zeitkomplexität

Die Verwendung einer Hashmap erfordert keine Sortierung, und die Schleife wird nur einmal ausgeführt, was zu O(n) Zeitkomplexität führt.

Die Hashmap hat jedoch möglicherweise, abhängig von den Eingaben, einen hohen Speicherbedarf. (Natürlich variiert die speichertechnische Komplexität je nach Implementierung der Hashmap.)

Finale Code

Hier ist die Implementierung in Go:

package main

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

// https://www.acmicpc.net/problem/3273 - Zwei Summen

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 {
		// Suche nach der Komplementzahl
		if _, ok := idxMap[target-num]; ok {
			count++
		}
		// Füge aktuellen Wert zur Hashmap hinzu
		idxMap[num] = i
	}

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

Fazit

Wir konnten das Problem mit Hash und Two Pointers lösen.

Ich habe dieses Problem erneut durchgearbeitet und zusammengefasst, weil ähnlichen Typen von Problemen bei Coding Tests auftreten können.

Ich habe dummerweise mit Methode 1 begonnen.🤣

(Vielleicht, weil ich lange kein Algorithmusproblem mehr gelöst habe, habe ich einfach zu einfach gedacht.)

Anschließend habe ich versucht, es mit Binary Search zu lösen, was nicht funktionierte, aber nach ein wenig Überlegung fand ich eine gute Lösung.

(Warum denke ich während einer Prüfung nie an solche Lösungen? ㅠㅠ)

Es wäre gut, ähnliche Probleme regelmäßig zu üben und sie zu dokumentieren, um bei Prüfungen hilfreich zu sein.

Hugh, weiter geht’s!