Cad é an teicníc dhá thréimhse?

Question

Accepted Answer

Úsáideann an teicníc **dhá thréimhse** dhá innéacs a bhogann trí sheicheamh chun fadhbanna a réiteach i bhpas amháin — ag tiontú go leor réitigh bhrúidiúla O(n²) go **O(n)**.

## An smaoineamh

Coinnigh dhá thréimhse (go minic ag na foircinn, nó ceann mall agus ceann tapa) agus bogann tú iad bunaithe ar choinníoll, ag laghdú an obair gan athrá.

## Sampla: péire a chuireann suas chuig sprioc i ngréine-eagar

```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
```

## Castacht

- **Am:** O(n). **Spás:** O(1).

## Cathain a úsáid / galair

Go hiontach do **ghréine-eagair**, seiceanna palindrome, inbhéartú, agus dúbailte a bhaint ar an áit. Ní mór an t-eagrán a bheith sórtáilte go minic don leagan pointéir dhiachasach. Bí cúramach le teorainneacha pointéir agus an coinníoll lúb (`lo < hi`).

## Cén fáth a bhíonn sé tábhachtach

Tá dhá thréimhse ar cheann de na patrúin agallamh is láidre: leagann sé droichead ar dhó lúba ar shiúlóid líneach geal.

Múineann sé duit struchtúr (mar shampla, sórtáil) a fhad is bhrú brúidiúla.

An smaoineamh céanna a dheanann cumadh, rannach, agus céim fhúisiúna sórtála fúisiúna.