مساله two sum
یکی از بهترین جاهایی که شما میتونید دانش برنامه نویسیتون رو محک بزنید و حتی تقویت کنید همینجاست! جایی که با مساله های مختلف روبرو میشید، ذهنتون رو به چالش میکشید و سعی میکنید با حل مساله و کدنویسیش دانشتون رو در برنامه نویسی بالاتر ببرید. در ادامه شما با اولین مساله آشنا میکنم، یعنی مساله two sum! این مساله از سایت leetcode انتخاب کردم و کدش رو در سه زبان مختلف براتون آماده کردم.
صورت مساله
به شما یک آرایه از اعداد صحیح (nums) و یک عدد صحیح (target) داده میشود. هدف این است که اندیسهای دو عدد را در این آرایه پیدا کنید که مجموع آنها برابر با عدد هدف (target) باشد. برای درک بهتر مساله 3 مثال زیر را نگاه کنید
مثال ۱:
ورودی: nums = [2,7,11,15]، هدف: 9
خروجی: [0,1]
توضیح: چون nums[0] + nums[1] = 9 است، بنابراین اندیسهای [0, 1] را برمیگردانیم.
مثال ۲:
ورودی: nums = [3,2,4]، هدف: 6
خروجی: [1,2]
مثال ۳:
ورودی: nums = [3,3]، هدف: 6
خروجی: [0,1]
در این مساله فرض میکنیم که دقیقا یک جواب وجود دارد و برای درست کردن تارگت نمیتوانیم از یک عنصر بیش از یک بار استفاده کنید.

قبل از اینکه جواب این مساله رو ببنید دو تا نکته بهتون بگم. این مساله رو به چند روش میشه حل کرد. من به دو روش براتون حل میکنم. اما قبلش پیشنهاد میکنم حتما بهش فکر کنید. اگه راه حلی به ذهنتون نرسید 3 تا راهنمایی هم بهتون میکنم. در ادامه ببینید:
راهنمایی
یک روش بسیار ساده و دم دستی روش بروت فورسه (brute force) یعنی تمام جفتهای ممکن از اعداد را بررسی کنید. این روش کنده.
برای پیدا کردن جفت اندیسها میتونید از ایده مکمل استفاده کنید. یعنی برای یک عدد ثابت مثل x کل آرایه رو بگردید و عدد y که برابر target – x رو پیدا کنید. شاید بگید که چه فرقی با قبلی داره؟ به این فکر کنید که برای جستجوی y چه کاری میشه کرد که سریعنر انجام بشه؟
این نکته در ادامه تکته قبلیه. برای اینکه جستجوی y (ایده راهنمایی 2) سریعتر بشه میتونید از hash map یا جدول هش استفاده کنید. قاعدتا باید hash map ها رو بلد باشید ولی اگه بلد نیستید آموزش یوتیوب رو ببینید.
روش 1 - بروت فورس (Brute Force)
در این روش تمام جفتهای ممکن از عناصر را بررسی کنیم که آیا مجموع آنها برابر با target (هدف) است یا خیر. برای این کار میتونیم از حلقههای تو در تو استفاده کنیم؛ به این صورت که حلقه بیرونی از اولین عنصر تا ماقبل آخر حرکت میکند و حلقه داخلی از عنصر بعدی تا آخرین عنصر رو پیمایش میکنه. این روش دارای پیچیدگی زمانی O(n^2) است. کد این روش رو با 3 زبان برنامه نویسی اینجا ببینید: