Cad é an teicníc an fhuinneog sleamhnaithe?

Question

IT Interview Practice · Accepted Answer

Cumhroinne **sliding-window** a choimeádann raon leanúnach (fuinneog) os cionn eolaire nó teanga agus sleamhnaíonn sí in ionad ríomhanna ó thús, ag réiteach go leor fadhbanna subarray/substring in **O(n)**.

## An smaoineamh

Leathnú an fhuinneog trí an imeall ar dheis a bhogadh; cúngaigh í trí an imeall ar chlé a bhogadh nuair a bhrísteann srian. Athúsáid an ríomh roimhe sin in ionad athscanadh.

## Sampla: suim uasta aon fhuinneog de mhéid k

```python
def max_window_sum(arr, k):
    window = sum(arr[:k])       # sum of first window
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]  # add new, drop old
        best = max(best, window)
    return best

max_window_sum([2, 1, 5, 1, 3, 2], 3)  # -> 9 (5+1+3)
```

## Castacht

- **Am:** O(n) — isteach agus amach ar an bhfuinneog a dhéanann gach eilimint uair amháin.
- **Spás:** O(1) do fhuinneoga socraithe, O(k) nuair a bhítear ag foluain an t-ábhar.

## Cathain a úsáid / galair

Úsáid do na fadhbanna "longest/shortest/max subarray le maoin X". Do fhuinneoga **athraitheach**, cuir chun cinn an pointeoir clé chun an srian a dhéanann a athbhunú. Bí aire do earráidí off-by-one agus eilimintí teorann a shuimiú/a bhaint.

## Cén fáth a bhíonn tábhacht ann

Baineann fuinneog sleamhnaithe obair dhomhain ar shiúl, ag iompú O(n·k) ríomhanta in aon phas amháin.

Is é an patrún roghanna do na fadhbanna teanga agus subarray a bhíonn i gcónaí i ndeilbhí agallamh.

An tuiscint — athúsáid an toradh roimhe sin in ionad ríomhána — a ghinealáil ar an teas agus ar bhardas an réamhtheolas.

An smaoineamh

Sampla: suim uasta aon fhuinneog de mhéid k

Castacht

Cathain a úsáid / galair

Cén fáth a bhíonn tábhacht ann

Ceisteanna gaolmhara