Suchalgorithmus Summe zweier Zahlen gleich x |
17.05.2016, 16:55 | Auf diesen Beitrag antworten » |
ubik | 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, 17:01 | Auf diesen Beitrag antworten » |
eulerscheZahl | 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. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|