Dviejų rodyklių technika naudoja dvi indeksus, kurie juda per seką, norint išspręsti problemas vienu praėjimu — daugelį O(n²) brute-force sprendimų paverčiant O(n).
Idėja
Palaikykite dvi rodykles (dažnai galuose arba vieną lėtą ir vieną greitą) ir judinkite jas pagal sąlygą, sumažindami darbą be perskenavimo.
Pavyzdys: poros, kurios suma lygi tikslui, paieška surūšiuotame masyve
():
lo, hi = , (arr) -
lo < hi:
s = arr[lo] + arr[hi]
s == target:
(lo, hi)
s < target:
lo +=
:
hi -=
two_sum_sorted([, , , , ], )
