Gegeven een gesorteerde lijst \((a_0,...,a_{n-1})\) van \(n\) gehele getallen. Bepaal drie verschillende indices \(p\), \(q\), \(r\) zodanig dat voor het triplet \((a_p, a_q, a_r)\) (indien deze bestaan) het volgende geldt: \(a_p + a_q + a_r = 0\).

Opgelet: de gesorteerde invoerlijst kan meerdere keren hetzelfde getal bevatten.

Ontwerp en implementeer een kwadratisch algoritme voor dit probleem.

Opgave

Schrijf een Python-functie zoekNulSomTriplet(gesorteerd: list). Deze functie neemt een gesorteerde lijst van gehele getallen als invoer en geeft een tuple van de indices terug. Indien er geen drie dergelijke elementen bestaan, moet de functie None teruggeven.

Voorbeelden

>>> zoekNulSomTriplet([-5, 1, 2, 3, 7, 8])
(0, 2, 3)
>>> zoekNulSomTriplet([ -16, -3, 2, 3, 5, 6, 7, 19])
(0, 1, 7)
>>> zoekNulSomTriplet([-16, -3, 2, 3, 5, 6, 7])
>>> zoekNulSomTriplet([-9, -8, -3, -1, 2, 5, 7, 13, 18])
(0, 4, 6)
>>> zoekNulSomTriplet([-4, -4, -2, 3, 5, 8, 10])
(0, 1, 5)
>>> zoekNulSomTriplet([-4, -4, 3, 5, 9, 10])
>>> zoekNulSomTriplet([])