حل Two Sum در پایتون؛ از دو حلقه تا دیکشنری، با دلیل هر خط

قرارداد مسئله را قبل از کد بنویس

ورودی این آموزش یک فهرست عدد صحیح و یک هدف عدد صحیح است. خروجی یک جفت اندیس یا None است. استفادهٔ دوباره از یک اندیس مجاز نیست. اگر چند جفت معتبر وجود داشته باشد، برگرداندن یکی از آن‌ها کافی است.

این قرارداد را با تمرین کلاس تطبیق بده؛ بعضی صورت‌ها تضمین می‌کنند جواب وجود دارد یا دقیقاً یک جواب داریم. تغییر قرارداد ممکن است نوع خروجی و مدیریت حالت بی‌جواب را عوض کند. تعریف روشن، جلوی بحث دربارهٔ یک کد برای دو مسئلهٔ متفاوت را می‌گیرد.

راه ساده: همهٔ جفت‌ها را بررسی کن

حلقهٔ اول یک عضو را انتخاب می‌کند و حلقهٔ دوم فقط عضوهای بعد از آن را می‌بیند. شروع j از i+1 باعث می‌شود یک اندیس دوبار استفاده نشود و جفت‌ها نیز دوبار بررسی نشوند.

تعداد جفت‌ها n(n−1)/2 است؛ پس زمان با مرتبهٔ n² رشد می‌کند. حافظهٔ کمکی ثابت است. این روش برای مرجع آزمون خوب است: ساده است و می‌توانیم خروجی روش سریع را با آن مقایسه کنیم.

def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return i, j
    return None

سؤال را عوض کن: چه مکملی قبلاً دیده‌ام؟

اگر عدد فعلی 7 و هدف 9 است، دنبال 2 می‌گردیم. لازم نیست دوباره همهٔ عضوهای قبلی را بگردیم؛ می‌توانیم آن‌ها را در دیکشنری نگه داریم. کلید، خود عدد و مقدار، اندیس آن است.

در هر دور، اول مکمل را بررسی می‌کنیم. اگر قبلاً دیده شده باشد، جفت پیدا شده است. اگر نه، عدد فعلی را ذخیره می‌کنیم و جلو می‌رویم. این ترتیب باعث می‌شود دیکشنری فقط عضوهای قبل از اندیس فعلی را داشته باشد.

def two_sum(nums, target):
    seen = {}
    for index, value in enumerate(nums):
        complement = target - value
        if complement in seen:
            return seen[complement], index
        seen[value] = index
    return None

اجرای [3, 2, 4] با هدف 6

قبل از دور اول، seen خالی است. برای 3 دنبال 3 می‌گردیم و چیزی پیدا نمی‌شود؛ سپس 3 را با اندیس صفر ذخیره می‌کنیم. برای 2 دنبال 4 می‌گردیم، هنوز نیست. برای 4 دنبال 2 می‌گردیم و اندیس یک را پیدا می‌کنیم. خروجی (1, 2) است.

چرا ذخیره کردن قبل از بررسی، خطاست؟

برای [3] و هدف 6، اگر اول seen[3]=0 را بنویسی و بعد مکمل 3 را بگردی، همان عضو را پیدا می‌کنی و ممکن است (0,0) برگردانی. جمع عددها درست است، اما قرارداد دو اندیس متفاوت نقض شده است.

برای [3,3] و هدف 6، ترتیب درست جواب می‌دهد: دور اول 3 ذخیره می‌شود؛ دور دوم مکمل را در عضو قبلی پیدا می‌کند. تکراری بودن عددها مشکلی ندارد؛ یکسان بودن اندیس‌ها مشکل است.

پیچیدگی را با فرضش توضیح بده

یک بار از روی n عضو عبور می‌کنیم و در هر دور یک جست‌وجوی دیکشنری داریم. با فرض زمان متوسط ثابت برای عملیات هش، زمان مورد انتظار O(n) است. seen در بدترین اندازه می‌تواند n عضو نگه دارد، پس حافظهٔ کمکی O(n) است.

«یک حلقه» به‌تنهایی دلیل O(n) نیست؛ کار داخل حلقه هم مهم است. اگر داخل حلقه از جست‌وجوی خطی در فهرست استفاده کنی، دوباره زمان می‌تواند درجهٔ دوم شود. توضیح پیچیدگی باید به عملیات واقعی کد وصل باشد.

تست فقط مثال صورت سؤال نیست

ورودی خالی، یک عضو، دو عدد برابر، عدد منفی و حالت بی‌جواب را بررسی کن. اگر چند پاسخ معتبر داریم، تست نباید صرفاً یک جفت خاص را قبول کند؛ باید قرارداد خروجی را بسنجد.

فایل کامل این مقاله، علاوه بر مثال‌ها، فهرست‌های کوچک شامل عددهای −2 تا 2 را با هدف‌های مختلف بررسی می‌کند و نتیجه را با جست‌وجوی همهٔ جفت‌ها تطبیق می‌دهد. این یک بررسی مستقل از منطق دیکشنری است.

python3 two_sum.py
# Two Sum: all checks passed

با ساروی تمرین کن، بدون گرفتن جواب فوری

این بار شرط را عوض کن: همهٔ جفت‌ها را می‌خواهیم یا تعداد جفت‌ها را؟ آیا فقط مقدار عددها مهم است یا اندیس‌ها؟ هرکدام مسئلهٔ تازه‌ای می‌سازد. اول مثال بنویس، بعد کد.

اگر کدت جواب غلط داد، ورودی خراب، خروجی فعلی و خروجی درست را کنار هم بده. از ساروی بخواه فقط اولین دوری را پیدا کند که قرارداد نقض می‌شود. برای فهم دیکشنری و تابع، آموزش پروژه‌ای پایتون را ادامه بده.