Menghitung Subarray dengan Jumlah Target
Menggabungkan jumlah awalan dengan hash map
Menghitung Subarray dengan Jumlah Target adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 3 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.
Pertanyaan yang Lebih Sulit
Sekarang tantangannya: hitung berapa banyak sublarik yang jumlahnya sama dengan target k. Memeriksa setiap pasangan memang lambat, tetapi jumlah prefiks ditambah peta hash dapat menyelesaikannya. 🎯
Rumuskan Ulang dengan Prefiks
Jumlah sublarik sama dengan prefix[r + 1] dikurangi prefix[l]. Jadi, jumlah sebesar k berarti ada dua nilai prefiks yang selisihnya tepat k.
Penyusunan Ulang Utama
Jika prefiks saat ini adalah P, Anda memerlukan prefiks sebelumnya yang sama dengan P dikurangi k. Penyusunan ulang itulah inti triknya.
need = current_prefix - kHitung, Jangan Mencari
Alih-alih menelusuri kembali setiap kali, ingat berapa kali setiap nilai prefiks telah muncul. Hitungan yang terus diperbarui memberikan jawaban dalam O(1).
Gunakan Peta Frekuensi
Kamus memetakan setiap nilai prefiks ke jumlah kemunculannya. Peta ini mengubah pencarian menjadi penghitungan seketika.
from collections import defaultdict
seen = defaultdict(int)Inisialisasi Prefiks Kosong
Sebelum loop, catat bahwa prefiks 0 telah muncul satu kali. Nilai awal ini memungkinkan sublarik yang dimulai dari indeks 0 ikut dihitung.
seen[0] = 1Loop Satu Lintasan
Untuk setiap elemen, perbarui prefiks berjalan, tambahkan jumlah kemunculan nilai yang diperlukan, lalu catat prefiks saat ini. Satu lintasan sudah menyelesaikan semuanya.
total += x
count += seen[total - k]
seen[total] += 1Mengapa Urutan Berpengaruh
Anda harus menambahkan ke jawaban sebelum mencatat prefiks saat ini. Jika tidak, rentang dengan panjang nol dapat ikut masuk dan hitungan menjadi salah.
Keuntungan Kecepatan
Setiap elemen memerlukan pekerjaan konstan, sehingga seluruh penghitungan berjalan dalam O(n). Cara ini mengungguli metode brute force O(n kuadrat) pada masukan besar.
Bilangan Negatif Tidak Masalah
Berbeda dari jendela geser, metode ini menangani bilangan negatif dengan baik karena selisih prefiks tetap valid apa pun tandanya.
Kasus Penggunaan Klasik
Pola ini menyelesaikan soal terkenal tentang sublarik dengan jumlah sama dengan k serta banyak varian tersamar di penguji kontes.
Pemeriksaan Cepat
Prefiks berjalan Anda adalah P dan targetnya adalah k.
Ringkasan
Anda dapat menghitung sublarik dengan jumlah target dalam O(n) menggunakan jumlah prefiks dan peta frekuensi. Inisialisasikan prefiks 0, lalu hitung sebelum mencatat. ✅
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Menghitung Subarray dengan Jumlah Target” gratis?
Ya — teks lengkap “Menghitung Subarray dengan Jumlah Target” 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 “Menghitung Subarray dengan Jumlah Target”?
Menggabungkan jumlah awalan dengan hash map 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 3 dari 4.
Berapa lama pelajaran “Menghitung Subarray dengan Jumlah Target” 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
- Membangun Array Jumlah Awalan
- Menjumlahkan Rentang Apa Pun dengan Pengurangan
- Menghitung Subarray dengan Jumlah Target
- Array Selisih untuk Pembaruan Rentang