Dua Penuding pada Tatasusunan Terisih
Gerakkan hujung ke dalam untuk mencapai sasaran.
Dua Penuding pada Tatasusunan Terisih ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 1 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.
Mengapa Dua Penuding
Teknik dua penuding mengimbas tatasusunan menggunakan dua indeks dan bukannya gelung bersarang, lalu menukarkan banyak idea O(n^2) menjadi satu lintasan O(n) yang kemas. 🎯
Tersusun ialah Kata Ajaib
Versi klasik memerlukan tatasusunan tersusun. Susunan membolehkan anda membuat pertimbangan: bergerak ke kanan meningkatkan nilai, manakala bergerak ke kiri mengurangkannya, jadi setiap langkah ialah keputusan sebenar.
Dua Penuding di Hujung
Mulakan satu penuding di hujung kiri dan satu lagi di hujung kanan. Kedua-duanya menghadap satu sama lain dan akan merapatkan jarak antara mereka secara beransur-ansur.
left = 0
right = len(a) - 1Gerakkan Hujung ke Dalam
Pada setiap langkah, anda menggerakkan tepat satu penuding ke arah dalam. Susunan tatasusunan memberitahu anda bahagian mana yang perlu digerakkan sedikit untuk mencapai matlamat.
Syarat Gelung
Teruskan gelung selagi left < right. Apabila kedua-duanya bertemu atau bersilang, setiap pasangan yang berguna telah diperiksa dan anda boleh berhenti.
while left < right:
# inspect a[left] and a[right]
passBaca Jumlah Semasa
Lihat a[left] + a[right] sebagai calon semasa anda. Membandingkannya dengan sasaran memberitahu anda sama ada nilai seterusnya perlu lebih besar atau lebih kecil.
total = a[left] + a[right]Terlalu Kecil: Gerakkan Penuding Kiri
Jika jumlah berada di bawah sasaran, anda memerlukan nilai yang lebih besar. Gerakkan penuding kiri ke kanan, ke arah nilai yang lebih besar, kerana tatasusunan diisih secara menaik.
if total < target:
left += 1Terlalu Besar: Gerakkan Penuding Kanan
Jika jumlah berada di atas sasaran, anda memerlukan nilai yang lebih kecil. Gerakkan penuding kanan ke kiri, ke arah nilai yang lebih kecil, untuk mengurangkan jumlah keseluruhan.
elif total > target:
right -= 1Setiap Langkah Membuang Kerja
Setiap gerakan menyingkirkan sekumpulan pasangan yang tidak perlu anda uji. Itulah sebabnya imbasan ini linear dan bukannya kuadratik.
Mengapa Ia Kekal Betul
Anda hanya membuang pasangan yang tidak mungkin sepadan, jadi jawapan yang betul tidak pernah terlepas. Jaminan ini menjadikan dua penuding boleh dipercayai dalam pertandingan.
Melangkaui Titik Hujung
Idea yang sama menggerakkan variasi: membalikkan susunan di tempat asal, membahagikan dan menggabungkan. Kuasai penuding yang bertemu ini, dan semuanya akan terasa biasa.
Semakan Pantas
Anda mengimbas tatasusunan tersusun dari kedua-dua hujung untuk mencari jumlah sasaran.
Ulang Kaji
Dua penuding mengimbas tatasusunan tersusun dari kedua-dua hujung, dengan menggerakkan salah satu daripadanya ke arah dalam pada setiap langkah selagi left < right. Linear, betul dan menjadi asas kepada banyak helah. 🚀
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 “Dua Penuding pada Tatasusunan Terisih” percuma?
Ya — teks penuh “Dua Penuding pada Tatasusunan Terisih” 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 “Dua Penuding pada Tatasusunan Terisih”?
Gerakkan hujung ke dalam untuk mencapai sasaran. 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 1 daripada 4.
Berapa lamakah pelajaran “Dua Penuding pada Tatasusunan Terisih” 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
- Dua Penuding pada Tatasusunan Terisih
- Cari Pasangan dengan Jumlah Diberi
- Buang Pendua di Tempat Asal
- Cantumkan Dua Jujukan Terisih