 Suchalgorithmus Summe zweier Zahlen gleich x |
ubik
Mitglied
Dabei seit: 10.04.2015
Beiträge: 41
 |
|
| Suchalgorithmus Summe zweier Zahlen gleich x |
     |
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 |
|
|
|
|
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 |
|
|
|
