Two pointers technique
Në shqip: Teknika e dy treguesve
ShpjegimiSQ
Te teknika e dy treguesve, mban dy pozicione në listë — shpesh njërin në fillim dhe tjetrin në fund — dhe i lëviz drejt njëri-tjetrit. Shumë probleme që duken O(n²) bëhen O(n).
EnglishEN
With the two pointers technique, you keep two positions in a list — often one at the start and one at the end — and move them towards each other. Many problems that look O(n²) become O(n).
Si ta mendosh
Si dy njerëz që e kërkojnë njëri-tjetrin në një korridor, duke u nisur nga dy skajet.
Lexoje në anglisht
Like two people looking for each other in a corridor, starting from opposite ends.
Shembull kodipython
def ka_shumen(v, s): # v e renditur
i, j = 0, len(v) - 1
while i < j:
if v[i] + v[j] == s: return True
i, j = (i + 1, j) if v[i] + v[j] < s else (i, j - 1)