Çfarë është teknika me dy tregues?

Question

Accepted Answer

Teknika me **dy tregues** përdor dy indekse që lëvizin nëpër një sekuencë për të zgjidhur probleme në një kalim të vetëm — kthejnë shumë zgjidhje brute-force O(n²) në **O(n)**.

## Ideja

Ruaj dy tregues (shpesh në skajet, ose një të ngadaltë dhe një të shpejtë) dhe lëvizi ato bazuar në një kusht, duke zvogëluar punën pa skanuar përsëri.

## Shembull: gjetja e një çifti që shtohet në një vlerë të synuar në një varg të renditur

```python
def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (lo, hi)       # found the pair
        elif s < target:
            lo += 1               # need a bigger sum
        else:
            hi -= 1               # need a smaller sum
    return None

two_sum_sorted([1, 3, 4, 6, 9], 10)   # -> (1, 3) for 4 + 6
```

## Kompleksiteti

- **Koha:** O(n). **Hapësira:** O(1).

## Kur të përdorni / kurthe

Mirë për **vargjet e renditur**, kontrolle palindromi, përmbysje dhe heqje të dyshimeve në vend. Vargu shpesh duhet të jetë i renditur për variantin me tregues konvergjues. Kujdes me kufijtë e treguesit dhe kushtin e ciklës (`lo < hi`).

## Pse ka rëndësi

Dy treguesit është një nga modelet me ndikimin më të lartë në intervista: apllon cikla të ngulitur në një skanim linear të pastër.

Ju mëson të shfrytëzoni strukturën (siç është renditja) në vend të brute force.

I njëjta ide e ushqen bashkimin, ndarjen dhe hapin e bashkimit të merge sort.