Informatiker Board | Algorithmen | Suchalgorithmus Summe zweier Zahlen gleich x

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Suchalgorithmus Summe zweier Zahlen gleich x

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Suchalgorithmus Summe zweier Zahlen gleich x
Beiträge zu diesem Thema	Autor	Datum
Suchalgorithmus Summe zweier Zahlen gleich x	ubik	17.05.2016 16:55
RE: Suchalgorithmus Summe zweier Zahlen gleich x	eulerscheZahl	17.05.2016 17:01

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

ubik
Mitglied

Dabei seit: 10.04.2015
Beiträge: 41

Suchalgorithmus Summe zweier Zahlen gleich x

Zitatantwort auf diesen Beitrag erstellen

Hallo,

ich soll ein Array durchlaufen und dabei Paare finden, dessen Summe gleich x ist.

Z. B.

Im Array

1,2,3,4,5,6

mit x = 5

finden sich
2,3 und 1,4.

Habt ihr eine Idee wie ich dies in O(n) Zeit umsetzen kann?

17.05.2016 16:55

Nehmen Sie ubik in Ihre Freundesliste auf

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

Du hast 2 Indizes. Der eine zeigt auf das erste Element (1) und der andere auf das letzte(6).
Die Summe von 1 und 6 ist größer als x=5, also musst du kleiner werden. Das heißt, du schiebst den zweiten Index nach links.
Das wiederholst du, bis die Indizes sich in der Mitte treffen.

Voraussetzung ist natürlich, dass das Array sortiert ist.

__________________
Syntax Highlighting fürs Board (Link)

17.05.2016 17:01

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Suchalgorithmus Summe zweier Zahlen gleich x