Silabus Pelajaran 55 dari 148 · Kecepatan tanpa cache
Kecepatan tanpa cache

Dua pointer, tanpa tabel

Kenapa ini penting "Cari dua hal yang jumlahnya X" punya jawaban terkenal: masukkan semuanya ke dalam set dan cari pasangannya. Ini cepat, dan butuh salinan semua data. Saat data sudah terurut, kamu hampir tidak butuh memori sama sekali.

A layanan hadiah menjual paket dua produk berbeda dengan harga paket tetap. Daftar harga produk sudah terurut, tidak ada duplikat, dan berada di perangkat tertanam dengan memori bebas yang sangat sedikit. Untuk harga paket, kamu butuh jumlah pasangan produk yang harganya jika dijumlahkan tepat sama dengan harga tersebut.

prices = [1, 2, 3, 4, 5, 6]   # sorted, no repeats
count_pairs(Tape(prices), 7)    # 3: (1, 6), (2, 5), (3, 4)
Giliranku

Tulis count_pairs(tape, target). tape adalah Tape dari harga bilangan bulat, diurutkan naik, tanpa duplikat. Kembalikan berapa banyak pasangan dua barang berbeda yang jumlahnya tepat target (setiap pasangan dihitung sekali). Budgets: untuk 20,000 item yang dibaca maksimal 60,000 nilai, dan gunakan maksimal 16,000 bytes memori kerja saat fungsi kamu berjalan (diukur dengan tracemalloc; set atau list dari 20,000 harga adalah lebih dari 150,000 bytes). len(tape) gratis.

Ada masalah di pelajaran ini? Laporkan · Tanya tentang pelajaran ini

Latihan ini akan segera dibuka

Selesaikan pelajaran sebelumnya agar pelajaran ini terbuka. Seluruh kursus ini gratis, tidak butuh akun, dan kamu bisa baca pelajaran ini sekarang.