Instead of recomputing a sum for every possible window, keep a running total: drop the value that just left the frame, add the value that just entered. One frame, sliding — not thousands of frames, recomputed.
← Back to the Field GuideHar bir mumkin bo'lgan window uchun sum'ni qaytadan hisoblash o'rniga, running total saqlang: freymdan chiqqan qiymatni ayiring, kirgan qiymatni qo'shing. Bitta freym siljiydi — minglab freym qayta hisoblanmaydi.
← Qo'llanmaga qaytishWatch the bars below: the dashed box is the current window sliding one step at a time — only the two edge values change each step, and the gold bars mark the best window found so far.
Quyidagi ustunlarga qarang: shtrixli quti — bir qadamda bir marta siljiydigan joriy window — har qadamda faqat ikkita chekka qiymat o'zgaradi, oltin ustunlar esa hozirgacha topilgan eng yaxshi window'ni belgilaydi.
k (given by the problem) and check that the array has at least k elements — with fewer than k elements, no window of that size exists.k elements directly: window_sum = sum(arr[0:k]). This one-time cost covers indices 0 through k - 1.best = window_sum, since it's the only window seen so far.i from k to len(arr) - 1, update the running total by subtracting the element leaving on the left, arr[i - k], and adding the element entering on the right, arr[i].[i - k + 1, i] — no re-summing needed — so compare it against best and update if it's better.i reaches the last index of the array; at that point every window of size k has been visited exactly once.best — a sum, a max, or (as in LC 643) an average obtained by dividing best by k.kni belgilang (masala bergan) va array'da kamida k ta element borligini tekshiring — k tadan kam element bo'lsa, shunday o'lchamdagi window umuman mavjud emas.k ta elementini to'g'ridan-to'g'ri qo'shib quring: window_sum = sum(arr[0:k]). Bu bir martalik xarajat 0 dan k - 1 gacha bo'lgan indekslarni qamrab oladi.best = window_sum deb belgilang, chunki bu hozircha ko'rilgan yagona window.i uchun (k dan len(arr) - 1 gacha), chapdan chiqib ketayotgan elementni, arr[i - k]ni, ayirib va o'ngdan kirib kelayotgan elementni, arr[i]ni, qo'shib running total'ni yangilang.[i - k + 1, i]ning yig'indisiga teng — qayta qo'shish shart emas — shuning uchun uni best bilan solishtiring va yaxshiroq bo'lsa yangilang.i array'ning oxirgi indeksiga yetguncha 4–5-qadamlarni takrorlang; shu nuqtada har bir k o'lchamdagi window aynan bir marta ko'rib chiqilgan bo'ladi.bestdan kelib chiqib qaytaring — yig'indi, maksimum, yoki (LC 643'dagidek) bestni kga bo'lish orqali olingan average.Time: O(n). Building the very first window costs O(k) — summing k elements once. After that, each of the remaining n - k slides does a fixed amount of work: one subtraction and one addition, regardless of how big k is. So the total work is O(k) + O(n - k) · O(1), which simplifies to O(n). Compare that to the brute-force approach of re-summing every window from scratch, which redoes O(k) work for each of the n - k + 1 windows — O(n·k) overall; sliding window collapses that k factor away entirely.
Space: O(1). The algorithm only ever tracks a running total and a best-so-far value (plus a loop index) — no matter how long the array is or how big k is, no extra array, hash map, or other structure that grows with the input is ever allocated.
Vaqt: O(n). Eng birinchi window'ni qurish O(k) turadi — k ta elementni bir marta qo'shish. Shundan keyin, qolgan n - k ta siljishning har biri belgilangan miqdordagi ish qiladi: bitta ayirish va bitta qo'shish, k qanchalik katta bo'lishidan qat'i nazar. Shunday qilib, jami ish O(k) + O(n - k) · O(1) bo'lib, bu O(n)ga soddalashadi. Buni har bir window'ni noldan qayta qo'shadigan brute-force yondashuv bilan solishtiring — u n - k + 1 ta window'ning har biri uchun O(k) ish takrorlaydi, jami O(n·k); sliding window esa bu k ko'paytuvchisini butunlay yo'q qiladi.
Xotira: O(1). Algoritm faqat running total va best-so-far qiymatini (va loop indeksini) kuzatib boradi — array qanchalik uzun yoki k qanchalik katta bo'lishidan qat'i nazar, kirish hajmiga qarab o'sadigan qo'shimcha array, hash map yoki boshqa struktura hech qachon yaratilmaydi.
sum(arr[i-k+1:i+1]) inside the loop) instead of updating the running total. Fix: only ever add the one incoming value and subtract the one outgoing value — re-summing the whole window throws away the entire point of the technique and silently turns O(n) back into O(n·k).i, the element leaving is arr[i - k] (the previous left edge), not arr[i - k + 1] or arr[i - 1]. Fix: write out a tiny example by hand (say k = 3, i = 5) and check the index arithmetic before trusting it in code.k, which leaves no valid window at all. Fix: check len(arr) >= k before building the first window, and decide up front what the function should return when it isn't (often 0, None, or an explicit error, depending on the problem).sum(arr[i-k+1:i+1])) — running total'ni yangilash o'rniga. Yechim: har doim faqat bitta kirib kelayotgan qiymatni qo'shing va bitta chiqib ketayotgan qiymatni ayiring — butun window'ni qayta qo'shish texnikaning butun mag'zini yo'qqa chiqaradi va O(n)ni sezilmagan holda yana O(n·k)ga aylantiradi.ida bo'lsa, chiqib ketayotgan element arr[i - k] (avvalgi chap chet), arr[i - k + 1] yoki arr[i - 1] emas. Yechim: qo'lda kichik misol yozing (aytaylik, k = 3, i = 5) va kodga ishonishdan oldin indeks arifmetikasini tekshiring.kdan qisqa bo'lishiga qarshi tekshiruvni unutish — bu holda hech qanday to'g'ri window mavjud emas. Yechim: birinchi window'ni qurishdan oldin len(arr) >= k ekanligini tekshiring va bu bo'lmasa funksiya nima qaytarishi kerakligini oldindan hal qiling (odatda 0, None, yoki masalaga qarab aniq xato).k. That's the direct fit for the fixed-size sliding window covered here.k uzunlikdagi har bir ketma-ket subarray yoki substring bo'yicha agregat — yig'indi, average, maksimum, minimum yoki mos kelishlar soni — so'raydi. Bu shu yerda ko'rib chiqilgan belgilangan o'lchamli sliding window uchun to'g'ridan-to'g'ri mos keladi.643. Maximum Average Subarray I ↗
Restated: given an integer array nums of length n and an integer k, find the contiguous subarray of length exactly k that has the maximum average value, and return that average. Any answer within 10⁻⁵ of the true value is accepted.
k, and you need the best average over every length-k subarray — that's the fixed-size sliding window pattern, not a brute-force scan of every possible window.sum / k) over windows of the same fixed size k is the same as maximizing the plain sum, since dividing by the same constant k never changes which window wins. So track the maximum sum, and only divide by k once, at the very end.window_sum = sum(nums[:k]) covers indices 0 through k - 1; set max_sum = window_sum as the best seen so far.i from k to len(nums) - 1, update window_sum += nums[i] - nums[i - k] (add the entering value, drop the leaving one), and update max_sum if window_sum is bigger.max_sum / k — the required average of the best window found.def findMaxAverage(nums, k):
# build the first window: sum of the first k elements (indices 0..k-1)
window_sum = sum(nums[:k])
max_sum = window_sum
# slide the window one index at a time across the rest of the array
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k] # add the value entering, drop the value leaving
max_sum = max(max_sum, window_sum)
return max_sum / k # convert the best sum into an average, once, at the end
643. Maximum Average Subarray I ↗
Qayta bayon: uzunligi n bo'lgan butun sonlar array'i nums va butun son k berilgan — average qiymati eng katta bo'lgan, uzunligi aynan k ga teng contiguous subarray'ni toping va o'sha average'ni qaytaring. Haqiqiy qiymatdan 10⁻⁵ farq bilan berilgan har qanday javob qabul qilinadi.
k, va sizga har bir uzunligi k bo'lgan subarray ustidan eng yaxshi average kerak — bu belgilangan o'lchamli sliding window pattern, har bir mumkin bo'lgan window'ni brute-force skanerlash emas.k o'lchamidagi window'lar ustida average'ni (sum / k) maksimallashtirish oddiy yig'indini maksimallashtirish bilan bir xil, chunki bir xil o'zgarmas kga bo'lish qaysi window g'olib chiqishini hech qachon o'zgartirmaydi. Shuning uchun maksimal yig'indini kuzating va faqat oxirida, bir marta, kga bo'ling.window_sum = sum(nums[:k]) 0 dan k - 1 gacha bo'lgan indekslarni qamraydi; hozircha ko'rilgan eng yaxshi natija sifatida max_sum = window_sum deb belgilang.i uchun (k dan len(nums) - 1 gacha), window_sum += nums[i] - nums[i - k] ni yangilang (kirib kelayotgan qiymatni qo'shing, chiqib ketayotganini tashlang), va window_sum kattaroq bo'lsa max_sumni yangilang.max_sum / k ni qaytaring — topilgan eng yaxshi window'ning talab qilingan average'i.def findMaxAverage(nums, k):
# build the first window: sum of the first k elements (indices 0..k-1)
window_sum = sum(nums[:k])
max_sum = window_sum
# slide the window one index at a time across the rest of the array
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k] # add the value entering, drop the value leaving
max_sum = max(max_sum, window_sum)
return max_sum / k # convert the best sum into an average, once, at the end
arr[i - k], where i is the new right edge) leaves and gets subtracted. Every other value already inside the window stays exactly as it was — it's never re-added or re-subtracted.left = right - k + 1), so the size never changes. A variable-size window has two independently controlled edges: the right edge expands to grow the window, and the left edge advances separately, on its own condition, to shrink it back — so the window's size changes over the course of the scan instead of staying fixed at k.arr[i - k] leaves. Before this slide, the window spanned indices [i - k, i - 1] (width k); after the slide it spans [i - k + 1, i]. The only index that was in the old window but isn't in the new one is i - k — that's the one dropped. arr[i - k + 1] is still inside both the old and the new window, so subtracting it would incorrectly remove a value that's still supposed to be counted.arr[i - k], bu yerda i — yangi o'ng chet) esa chiqadi va ayiriladi. Window ichida allaqachon bo'lgan boshqa har qanday qiymat aynan o'zgarishsiz qoladi — u hech qachon qayta qo'shilmaydi yoki qayta ayirilmaydi.left = right - k + 1), shuning uchun o'lcham hech qachon o'zgarmaydi. O'zgaruvchan o'lchamli window'da esa ikkita mustaqil boshqariladigan chet bor: o'ng chet window'ni kengaytirish uchun kengayadi, chap chet esa uni qisqartirish uchun o'z sharti bo'yicha alohida siljiydi — shuning uchun window'ning o'lchami skanerlash davomida kda qat'iy turmasdan o'zgarib boradi.arr[i - k] chiqadi. Shu siljishdan oldin window [i - k, i - 1] indekslarini qamrab olgan edi (kengligi k); siljishdan keyin u [i - k + 1, i]ni qamraydi. Eski window'da bo'lib, yangisida bo'lmagan yagona indeks — i - k; aynan shu tashlab yuboriladi. arr[i - k + 1] esa hali ham eski va yangi window'ning ikkalasida ham bor, shuning uchun uni ayirish hali ham hisoblanishi kerak bo'lgan qiymatni noto'g'ri olib tashlagan bo'lardi.