Kira Subtatasusunan dengan Jumlah Sasaran
Gabungkan jumlah awalan dengan peta cincang.
Kira Subtatasusunan dengan Jumlah Sasaran ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 3 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.
Soalan yang Lebih Sukar
Inilah kelainannya: kira berapa banyak subtatasusunan yang jumlahnya sama dengan sasaran k. Memeriksa setiap pasangan adalah lambat, tetapi jumlah awalan bersama peta cincang dapat menyelesaikannya. 🎯
Susun Semula dengan Awalan
Jumlah subtatasusunan bersamaan dengan prefix[r + 1] tolak prefix[l]. Jadi, jumlah k bermaksud dua nilai prefix berbeza tepat sebanyak k.
Penyusunan Semula Utama
Jika prefix semasa ialah P, Anda memerlukan prefix terdahulu yang sama dengan P tolak k. Penyusunan semula itu ialah keseluruhan helahnya.
need = current_prefix - kKira, Jangan Cari
Daripada mengimbas ke belakang setiap kali, ingat kekerapan setiap nilai prefix yang telah muncul. Kiraan berjalan ini memberikan jawapan dalam O(1).
Gunakan Peta Kekerapan
Kamus memetakan setiap nilai prefix kepada bilangan kemunculannya. Peta ini menukarkan carian kepada pengiraan serta-merta.
from collections import defaultdict
seen = defaultdict(int)Mulakan Prefix Kosong
Sebelum gelung bermula, catat bahawa prefix 0 telah muncul sekali. Nilai permulaan ini membolehkan subtatasusunan yang bermula pada indeks 0 dikira.
seen[0] = 1Gelung Satu Laluan
Bagi setiap elemen, kemas kini prefix berjalan, tambahkan kiraan nilai yang diperlukan, kemudian catat prefix semasa. Satu laluan menyelesaikan semuanya.
total += x
count += seen[total - k]
seen[total] += 1Sebab Susunan Langkah Penting
Anda mesti menambahkannya kepada jawapan sebelum mencatat prefix semasa. Jika tidak, julat berpanjang sifar akan terselit dan kiraan menjadi salah.
Kelebihan Kelajuan
Setiap elemen memerlukan kerja masa malar, jadi keseluruhan pengiraan berjalan dalam O(n). Ini mengatasi kaedah cuba semua pasangan O(n kuasa dua) bagi masukan besar.
Nombor Negatif Tidak Mengapa
Tidak seperti tetingkap gelongsor, kaedah ini mengendalikan nombor negatif dengan baik kerana perbezaan prefix kekal sah tanpa mengira tandanya.
Contoh Kegunaan Klasik
Pola ini menyelesaikan masalah terkenal jumlah subtatasusunan bersamaan k serta banyak variasi yang disamarkan dalam sistem penilai pertandingan.
Semakan Pantas
Prefix berjalan Anda ialah P dan sasaran ialah k.
Ringkasan
Anda boleh mengira subtatasusunan yang jumlahnya sama dengan sasaran dalam O(n) menggunakan jumlah awalan dan peta kekerapan. Mulakan dengan prefix 0, kemudian kira sebelum mencatat. ✅
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 “Kira Subtatasusunan dengan Jumlah Sasaran” percuma?
Ya — teks penuh “Kira Subtatasusunan dengan Jumlah Sasaran” 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 “Kira Subtatasusunan dengan Jumlah Sasaran”?
Gabungkan jumlah awalan dengan peta cincang. 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 3 daripada 4.
Berapa lamakah pelajaran “Kira Subtatasusunan dengan Jumlah Sasaran” 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
- Bina Tatasusunan Jumlah Awalan
- Jumlahkan Sebarang Julat dengan Penolakan
- Kira Subtatasusunan dengan Jumlah Sasaran
- Tatasusunan Perbezaan untuk Kemas Kini Julat