Tetingkap Berubah dengan Dua Penuding
Besarkan dan kecilkan untuk memenuhi syarat.
Tetingkap Berubah dengan Dua Penuding ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 2 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apabila Tetingkap Boleh Mengembang
Sesetengah masalah tidak menetapkan panjang tetingkap. Sebaliknya, tetingkap mengembang dan mengecil untuk mengekalkan sesuatu syarat, seperti jumlah yang kekal di bawah had.
Dua Penuding, Satu Tetingkap
Simpan dua indeks, kiri dan kanan, yang menandakan tepi tetingkap. Penuding kanan mengembangkan tetingkap, manakala penuding kiri mengekori di belakang untuk mengecilkannya apabila perlu.
left = 0
window = 0Kembangkan ke Kanan
Bergerak ke kanan merentasi setiap unsur dan masukkannya ke dalam tetingkap. Kemas kini keadaan berjalan Anda, seperti menambah nilai baharu pada jumlah.
for right in range(n):
window += a[right]Kecilkan Apabila Perlu
Selagi tetingkap melanggar peraturan, gerakkan kiri ke kanan dan keluarkan unsur tersebut. Ini memulihkan syarat tanpa perlu berpatah balik.
while window > limit:
window -= a[left]
left += 1Baca Tetingkap yang Sah
Apabila gelung dalaman tamat, tetingkap dari kiri hingga kanan adalah sah. Panjangnya ialah kanan tolak kiri tambah satu dan sedia digunakan.
length = right - left + 1Catat yang Terbaik
Kemas kini jawapan Anda dengan tetingkap sah ini, yang selalunya merupakan tetingkap terpanjang yang ditemui. Lakukan ini pada setiap lelaran supaya tiada yang terlepas.
best = max(best, right - left + 1)Mengapa Ia Linear
Setiap penuding hanya bergerak ke hadapan, tidak pernah berundur. Penuding kiri dan kanan bergerak ke hadapan sebanyak paling banyak n langkah secara keseluruhan, jadi seluruh imbasan ialah O(n).
Syarat Monoton
Ini berfungsi apabila memanjangkan tetingkap hanya menjadikan syarat itu lebih sukar untuk dipenuhi. Tingkah laku monoton inilah yang membolehkan kiri tidak perlu berundur.
Terpanjang berbanding Terpendek
Untuk mencari tetingkap sah yang terpendek, kecilkan tetingkap selagi peraturan masih dipenuhi dan catat jawapan sebelum syarat dilanggar. Mekanik penuding kekal sama.
while window >= target:
best = min(best, right - left + 1)
window -= a[left]
left += 1Berwaspada terhadap Tetingkap Kosong
Jika pengecilan boleh mengosongkan tetingkap, pastikan Anda menghalang kiri melepasi kanan. Pastikan juga jawapan benar-benar ditemui sebelum memulangkannya.
Kenal Pasti Coraknya
Pilih tetingkap boleh ubah apabila masalah meminta rentetan berdampingan yang terpanjang atau terpendek dan memenuhi syarat pada unsurnya.
Semakan Pantas
Anda menjalankan tetingkap boleh ubah dengan dua penuding pada tatasusunan bersaiz n.
Ringkasan
Kembangkan kanan untuk memasukkan unsur, kecilkan kiri apabila peraturan dilanggar, dan catat setiap tetingkap yang sah. Penuding yang hanya bergerak ke hadapan mengekalkan kerumitan O(n). ✅
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Tetingkap Berubah dengan Dua Penuding” percuma?
Ya — teks penuh “Tetingkap Berubah dengan Dua Penuding” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Tetingkap Berubah dengan Dua Penuding”?
Besarkan dan kecilkan untuk memenuhi syarat. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 2 daripada 4.
Berapa lamakah pelajaran “Tetingkap Berubah dengan Dua Penuding” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Jumlah Tetingkap Saiz Tetap
- Tetingkap Berubah dengan Dua Penuding
- Subrentetan Terpanjang Tanpa Ulangan
- Kira Tetingkap yang Memenuhi Peraturan