Sliding-window పద్ధతి ఏమిటి?

Question

Accepted Answer

**Sliding-window** పద్ధతి ఒక శ్రేణి లేదా స్ట్రింగ్ మీద ఒక నిరంతర పరిధిని (విండో) నిర్వహిస్తుంది మరియు దానిని స్లైడ్ చేస్తుంది, ఎందుకంటే మొదటి నుండి తిరిగి లెక్కించడానికి బదులుగా, అనేక subarray/substring సమస్యలను **O(n)** లో పరిష్కరిస్తుంది.

## ఆలోచన

విండోను కుడి అంచుని కదిలించడం ద్వారా విస్తరించండి; నిర్బంధం ఉల్లంఘించబడినప్పుడు ఎడమ అంచుని కదిలించడం ద్వారా సంకోచించండి. మళ్లీ స్కాన్ చేయకుండా మునుపటి గణనను తిరిగి ఉపయోగించుకోండి.

## ఉదాహరణ: 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)
```

## సంక్లిష్టత

- **సమయం:** O(n) — ప్రతి మూలకం విండోలోకి ఒక్కసారి ప్రవేశిస్తుంది మరియు వేయబడుతుంది.
- **స్థలం:** స్థిర విండోల కోసం O(1), కంటెంట్‌ను ట్రాక్ చేస్తున్నప్పుడు O(k).

## ఎప్పుడు ఉపయోగించాలి / pitfalls

"X ఆస్తితో సबారే పొడవైన/చిన్న/గరిష్ట" సమస్యల కోసం ఉపయోగించండి. **వేరియబల్** విండోల కోసం, నిర్బంధాన్ని పునరుద్ధరించడానికి ఎడమ పాయింటర్‌ను ముందుకు కదిలించండి. సరిహద్దు మూలకాలను జోడించేటప్పుడు/తీసివేసేటప్పుడు off-by-one లోపాల కోసం చూడండి.

## ఇది ఎందుకు ముఖ్యమైనది

Sliding window పునరావృత్తమయ్యే పనిని నిర్మూలిస్తుంది, O(n·k) పునర్గణన ఒక పాసుగా మారుతుంది.

ఇది substring మరియు subarray సమస్యల కోసం go-to నమూనా, ఇవి సంభాషణలలో నిరంతరం కనిపిస్తాయి.

অంతర్దృష్టి — పునర్గణన చేయకుండా మునుపటి ఫలితాన్ని తిరిగి ఉపయోగించుకోండి — స్ట్రీమింగ్ మరియు రీయల్-టైమ్ ডేటాకు సాధారణీకరిస్తుంది.