स्लाइडिङ-विन्डो प्रविधि के हो?

Question

Accepted Answer

**स्लाइडिङ-विन्डो** प्रविधिले एरे वा स्ट्रिङ्गमा एक सन्निहित दायरा (विन्डो) राखेर त्यसलाई स्लाइड गर्छ र शुरुबाट पुनः गणना गरी हराउँछ, धेरै सबएरे/सबस्ट्रिङ् समस्याहरूलाई **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 सहित सबैभन्दा लामो/सबैभन्दा छोटो/अधिकतम सबएरे" समस्याहरूको लागि प्रयोग गर्नुहोस्। **परिवर्तनशील** विन्डोहरूको लागि, बाध्यता पुनः स्थापित गर्न बाँयाँ सूचक अग्रिम गर्नुहोस्। सीमान्त तत्व थप्दा/हटाउँदा off-by-one त्रुटिहरूको ध्यान राख्नुहोस्।

## किन यो महत्त्वपूर्ण छ

स्लाइडिङ विन्डोले अनावश्यक काम हटाएर, O(n·k) पुनः गणनालाई एक पास मा परिणत गर्छ।

यो सबस्ट्रिङ् र सबएरे समस्याहरूको लागि जाने-जाना प्रविधि हो जुन साक्षात्कारमा निरन्तर उपस्थित हुन्छ।

अन्तर्दृष्टि — पहिलेको परिणाम पुनः प्रयोग गर्नुहोस् र पुनः गणना गरी हराउनुहोस् — स्ट्रिमिङ र वास्तविक-समय डेटामा सामान्यकृत गर्छ।