Jumlah Window Berukuran Tetap
Menggeser window sepanjang k dalam O(n)
Jumlah Window Berukuran Tetap adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Masalah Penjumlahan Berulang
Banyak tugas meminta jumlah setiap blok yang terdiri dari k elemen berurutan. Menghitung ulang setiap blok dari awal akan boros, dan Anda dapat melakukannya dengan lebih baik. 🪟
Cara Lambat Terlebih Dahulu
Gagasan naifnya adalah menjumlahkan setiap jendela dengan panjang k secara terpisah. Cara ini mengulang pekerjaan dan membutuhkan O(n kali k), yang terlalu lambat untuk masukan berukuran besar.
for i in range(n - k + 1):
s = sum(a[i:i + k])Wawasan Utama
Jendela yang bersebelahan hampir sepenuhnya tumpang tindih. Saat bergeser satu langkah ke kanan, Anda hanya perlu menghapus elemen paling kiri dan menambahkan satu elemen baru di kanan.
Siapkan Jendela Pertama
Mulailah dengan menjumlahkan k elemen pertama satu kali. Jumlah tunggal ini akan terus Anda perbarui saat jendela bergeser maju.
window = sum(a[:k])
best = windowGeser Satu Langkah
Untuk menggeser jendela, tambahkan elemen yang masuk dan kurangi elemen yang keluar. Dengan demikian, setiap langkah hanya membutuhkan pekerjaan konstan O(1).
for i in range(k, n):
window += a[i] - a[i - k]Lacak Jawaban Anda
Setelah setiap pergeseran, perbarui apa pun yang diperlukan, misalnya jumlah maksimum jendela yang telah ditemukan sejauh ini. Nilai jendela selalu tersedia secara langsung.
best = max(best, window)Total Biayanya Linear
Anda mengakses setiap elemen untuk menambahkannya, lalu mengaksesnya sekali lagi untuk menghapusnya, sehingga seluruh penelusuran adalah O(n). Cara ini dengan mudah memenuhi batasan masukan besar.
Perhatikan Indeks
Elemen yang keluar dari jendela adalah a[i - k], bukan a[i - 1]. Mendapatkan pergeseran ini dengan benar adalah kesalahan paling umum pada jendela tetap.
Rata-Rata Didapatkan Sekaligus
Ingin mendapatkan rata-rata jendela maksimum, bukan jumlahnya? Cukup bagi jumlah jendela yang dilacak dengan k. Logika jendela geser sama sekali tidak berubah.
avg = window / kTangani Larik Kecil
Jika larik lebih pendek daripada k, tidak ada jendela penuh. Bandingkan len(a) dengan k sejak awal dan segera kembalikan hasil untuk menghindari kesalahan indeks.
if n < k:
return NoneKapan Jendela Tetap Cocok
Gunakan pola ini kapan pun panjang jendela tetap dan nilai dapat digabungkan dengan murah, seperti jumlah, hitungan, atau statistik berjalan sederhana.
Pemeriksaan Cepat
Anda menggeser jendela berukuran k satu langkah ke kanan melintasi sebuah larik.
Ringkasan
Siapkan jendela pertama satu kali, lalu tambahkan dan kurangi pada setiap langkah untuk menggesernya dalam O(1). Seluruh penelusuran berukuran tetap berjalan dalam waktu linear. ✅
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Jumlah Window Berukuran Tetap” gratis?
Ya — teks lengkap “Jumlah Window Berukuran Tetap” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Jumlah Window Berukuran Tetap”?
Menggeser window sepanjang k dalam O(n) Kamu berlatih Competitive Programming Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Competitive Programming Academy?
Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.
Berapa lama pelajaran “Jumlah Window Berukuran Tetap” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Jumlah Window Berukuran Tetap
- Window Variabel dengan Two Pointer
- Substring Terpanjang Tanpa Pengulangan
- Menghitung Window yang Memenuhi Aturan