برای دسترسی به سوال 1 لیت‌کد میتونید از این لینک استفاده کنید. سطح این سوال Easy است.

اگر پیشنهادی برای اصلاح پست دارید، می‌تونید از طریق دکمه‌ی "پیشنهاد اصلاح متن" وارد ریپازیتوری وبلاگ در github بشید و تغییرات مورد نظرتون رو پیشنهاد بدید.

شرایط مسئله

در این مرحله، شرایط خاص مسئله و حالت‌های edge case رو بررسی می‌کنیم. این شرایط باید در توضیحات سوال یا مثال‌ها مشخص شده باشن یا اینکه از پاسخ‌های پیش فرض استفاده کنیم.

  • آیا همه اعداد مثبت هستن یا میتونن صفر و منفی هم باشن؟ همه اعداد مثبت هستن. 
  • آیا اعداد تکراری هم داریم یا همه یونیک هستن؟ همه اعداد یونیک هستن.
  • آیا همواره جوابی با شرایط خواسته شده داریم یا ممکنه مسئله بی جواب باشه؟ ممکنه مسئله جواب نداشته باشه. این موضوع از چند جهت مهمه، مثلا ممکنه دو عدد با شرط خواسته شده در آرایه پیدا نشه، یا ممکنه آرایه اصلا عضوی نداشته باشه، یا ممکنه آرایه تک عضوی باشه. ما حتما دو عضو میخوایم که مجموعشون برابر target بشه.
  • اگه مسئله جواب نداشت چی برگردونیم؟ null، عدد -1، آرایه خالی یا …؟ اگه جواب وجود نداشت null برگردون.
  • آیا ممکنه چند جفت عدد وجود داشته باشن که مجموعشون برابر تارگت بشه؟ خیر، حداکثر یک جفت عدد با شرط گفته شده خواهیم داشت.

نوشتن test case

در این مرحله، چند مثال می‌نویسیم که هم شرایط خواسته شده و هم edge case هایی که بالاتر اشاره کردیم رو pass کنه.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
input = [1,3,7,9,2] , target = 11
output = [3,4]
input = [1,3,7,9,2] , target = 25
output = null
input = [] , target = 1
output = null
input = [5] , target = 5
output = null
input = [1,6] , target = 7
output = [0,1]

راه حل منطقی

در این مرحله به دنبال working solution هستیم، یعنی راه حلی منطقی که بتونه مسئله رو حل کنه. به راه حل بهینه فکر نمی‌کنیم. درگیر زبان برنامه نویسی و محدودیت‌های اون هم نخواهیم بود.

مثال اول رو که best case هست بررسی می‌کنیم. چطور مطمئن بشیم که جفت عددی توی آرایه هست که جمعشون برابر تارگت بشه؟ راحت‌ترین کار اینه که تمام جفت اعداد رو جمع کنیم و ببینیم جمعشون برابر تارگت میشه یا نه؟ مثلا 1 رو با تک تک اعضای دیگه جمع میکنیم و میبینیم هیچکدوم برابر 11 نمیشه، پس پاسخ نهایی ما شامل 1 نخواهد بود. 3 رو با تک تک اعضا جمع میکنیم و میبینیم برابر 11 نمیشه، پس پاسخ نهایی شامل عدد 3 نخواهد بود.

به این تکنیک two pointers میگن. دو تا پوینتر داریم که نحوه حرکتشون بستگی به راه حل ما داره و کل جواب مسئله همینه! پوینتر اول روی 1 قرار میگیره و پوینتر دوم روی عنصر دوم و سوم و… آرایه جلو میره. هر بار چک میکنه که آیا مجموع عددی که پوینتر یک و پوینتر دو نشون میدن برابر تارگت هست یا نه؟ اگه باشه، indexشون رو برمیگردونه.

اما هیچ جوابی شامل 1 نیست، پس عملا 1 از آرایه خط میخوره و دیگه در پیمایشهای بعدی اونو چک نمیکنیم. در ادامه، پوینتر یک روی عدد 3 قرار میگیره. اما پوینتر دو روی عدد 1 قرار نمیگیره چون میدونیم که هیچ جفت جوابی شامل عدد 1 نیست و 1 عملا خط خورده! پوینتر دوم میره روی عدد 7 و دوباره روال قبلی تکرار میشه اما بازم جواب پیدا نشد. پوینتر اول میره روی 7 و پوینتر دوم میره روی 9. جواب پیدا نشد. پوینتر دوم میره روی 2. بازم جواب پیدا نشد. پس 7 هم خط میخوره. پوینتر اول میره روی 9 و پوینتر دوم میره روی 2. حاصل جمع 9 و 2 میشه 11 که جوابه. پس باید اندیسهای پوینتر اول و دوم رو به عنوان جواب برگردونیم.

تبدیل راه حل به کد

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
const findTwoSum = function(nums, target) {
    for (let p1 = 0; p1 < nums.length; p1++) {
        const numberToFind = target - nums[p1];
        for (let p2 = p1 + 1; p2 < nums.length; p2++) {
            if (numberToFind === nums[p2]) {
                return [p1, p2];
            }
        }
    }
    return null;
};

پیچیدگی زمانی و حافظه‌ای

در این مرحله به بررسی پیچیدگی زمانی و حافظه ای راه حل می‌پردازیم. یعنی تحلیل می‌کنیم که بین زمان اجرای الگوریتم و حافظه مصرفی آن، چه رابطه ای با اندازه ورودی الگوریتم وجود دارد.

ما دو لوپ for داریم. لوپ اول به تعداد اعضای آرایه یعنی n اجرا میشه. لوپ دوم درون لوپ اول قرار گرفته و اون هم از مرتبه n است. اما لوپ دوم که به تک تک اعضای آرایه که n تاست کاری نداره، پس چرا اون رو هم n در نظر گرفتیم؟ اگه بخواهیم الگوریتم از یه مرتبه زمانی نباشه، باید به مرتبه پایینترش بره. مرتبه پایینتر از n میشه logn. ولی لوپ دوم نمیتونه logn باشه. چرا؟ چون log در کامپیوتر مبنای 2 داره و اگه با هر بار جلو رفتن در لوپ، تعداد عملیات نصف میشد، اونوقت میشد logn. اما هر بار نصف نمیشه و فقط یدونه ازش کم میشه. در واقع یه ذره کمتر از n میشه که چون ما قراره O (بدترین حالت) رو در نظر بگیریم، همون n در نظر میگیریمش. پس مرتبه زمانی کل الگوریتم میشه O(n2).

بهینه‌سازی

آیا میشه الگوریتم رو به مرتبه پایینتر یعنی nlogn برد؟ لوپ اول که n هست، آیا دومی رو میشه logn کرد؟ یعنی هر بار عملیات های مورد نظر براش نصف بشه؟ راهی به ذهنم نمیرسه. مرتبه بعدی n هست. یعنی کلا لوپ دوم حذف بشه؟ آیا ایده ای داریم براش؟

مهمترین هزینه الگوریتم ما، دو لوپ for هستن. باید دقیق بفهمیم که دارن چکار میکنن. آیا راهی هست که بشه یکی رو حذف کرد یا با هم ادغامشون کرد؟ لوپ اول پوینتر اول رو تنظیم میکنه و عدد numbetToFind رو ست میکنه. لوپ دوم پوینتر دوم رو تنظیم میکنه و عدد numbetToFind رو با عددی که در جایگاه پوینتر دوم هست مقایسه میکنه. اگه برابر باشن جواب پیدا شده.

وقتی پوینتر اول میره روی عنصر دوم و سوم و چهارم و… باید یه جوری با چیزهایی که قبلا چکشون کرده مقایسه بشه. ایده همینه. پس باید چیزی مثل حافظه داشته باشیم. در الگوریتم‌ها Hashmap خیلی کاربرد داره برای بهینه کردن. در سی شارپ میشه Dictionary. هر عنصری که ازش رد میشیم رو در اون ذخیره میکنیم تا بعدا دوباره محاسبات انجام ندیم و صرفا مقایسه کنیم. توی این دیکشنری چی اضافه کنیم؟ key اش همون عنصریه که دنبالش هستیم و value اش، ایندکس‌اش است.

به عنوان مثال، وقتی روی 1 هستم، حاصل (1-11) رو حساب میکنم که میشه 10. حالا key رو 10 میذارم و value رو ایندکس 1 یعنی 0 میذارم. این چه کمکی میکنه؟ به بعدی که برم میگم چک کن آیا توی کلیدها 10 داریم یا نه؟ اگه داریم، ایندکسش رو بده که همین الان جواب رو برگردونیم. در این حالت مرتبه زمانی الگوریتم به O(n) میرسه.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
const findTwoSum = function(nums, target) {
    const numsMap = {};
    for (let p = 0; p < nums.length; p++) {
        const currentMapVal = numsMap[nums[p]];
        if (currentMapVal >= 0) {
            return [currentMapVal, p];
        } else {
            const numberToFind = target - nums[p];
            numsMap[numberToFind] = p;
        }
    }
    return null;
}

منابع

udemy