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)।

## எப்போது பயன்படுத்த / பயணிப்புக்கு

"X சொத்து கொண்ட மிக நீண்ட/குறுகிய/பெரிய subarray" சிக்கல்களுக்குப் பயன்படுத்தவும்। **மாறிக்கூடிய** சாளரங்களுக்கு, கட்டுப்பாட்டை மீட்டெடுக்க இடது சுட்டியை நகர்த்தவும். எல்லை உபாதுக்களைச் சேர்க்கும்/அகற்றும் போது off-by-one பிழைகளைக் கவனியுங்கள்।

## ஏன் இது முக்கியம்

Sliding window தேவையற்ற வேலையை நீக்குகிறது, O(n·k) மீண்டும் கணக்கீட்டை ஒரு பாஸாக மாற்றுகிறது.

இது substring மற்றும் subarray சிக்கல்களுக்கான go-to முறை, இது பேட்டிகளில் தொடர்ந்து தோன்றுகிறது.

অন்தர்দृष्टி — மீண்டும் கணக்கிடுவதற்கு பதிலாக முந்தைய முடிவை மீண்டும் பயன்படுத்தவும் — ஸ்ட்ரீமிং மற்றும் நிஜ-நேர தரவுக்கு பொதுமைப்படுத்துகிறது.