سرفصل‌ها درس 55 از 148 · سرعت بدون کش
سرعت بدون کش

دو اشاره، بدون جدول

چرا اهمیت دارد: مسئله «دو چیز را پیدا کن که مجموعشان X شود» پاسخ معروفی دارد: همه چیز را در یک مجموعه قرار بده و شریکش را پیدا کن. این روش سریع است و به کپی تمام داده‌ها نیاز دارد. وقتی داده‌ها مرتب باشند، تقریباً به هیچ حافظه‌ای نیاز نیست.

یک سرویس هدیه بسته‌های متشکل از دو محصول مختلف را با قیمت ثابت بسته می‌فروشد. فهرست قیمت محصولات مرتب است، هیچ تکراری ندارد و روی یک دستگاه تعبیه‌شده با حافظه آزاد بسیار کم قرار دارد. برای هر قیمت بسته، شما به تعداد جفت محصول‌هایی نیاز دارید که قیمت‌شان دقیقاً به آن قیمت برسد.

prices = [1, 2, 3, 4, 5, 6]   # sorted, no repeats
count_pairs(Tape(prices), 7)    # 3: (1, 6), (2, 5), (3, 4)
نوبت شما

نوشتن count_pairs(tape, target). tape است یک Tape از قیمت‌های عددی صحیح، مرتب‌شده صعودی و بدون تکرار. بازگردانید چند جفت از دو آیتم مختلف جمع می‌شوند تا دقیقاً target (هر جفت یک‌بار شمارش می‌شود). بودجه‌ها: برای ۲۰٬۰۰۰ مورد حداکثر ۶۰٬۰۰۰ مقدار بخوانید و در حین اجرای تابع خود حداکثر ۱۶٬۰۰۰ بایت حافظهٔ کاری مصرف کنید (اندازه‌گیری‌شده با tracemalloc؛ یک مجموعه یا لیست از ۲۰٬۰۰۰ قیمت بیش از ۱۵۰٬۰۰۰ بایت خواهد بود). len(tape) رایگان است.

مشکلی در این درس دیدید؟ گزارشش کنید · دربارهٔ این درس بپرسید

این تمرین به‌زودی باز می‌شود

درس پیش از آن را تمام کنید تا این یکی باز شود. کل دوره رایگان است، حساب کاربری لازم نیست، و می‌توانید همین الان این درس را بخوانید.