کدچلنچ - دو جمع (Two Sum)

سلام رفقا، توی این مقاله قصد دارم یکی از چالش های LeetCode رو که با جاوا اسکریپت حل کردم رو براتون شرح بدم. حالا بریم با هم مسئله رو حل کنیم. سعی کنید قبل از خوندن جواب، در موردش فکر کنید و تمرین کنید. سطح مسئله : ساده

مسئله

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

مثال ۱:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

مجموع nums[0] با nums[1] برابر با ۹ که عدد تارگت هست، ما ایندکس [0,1] رو برمیگردونیم.

مثال ۲:

Input: nums = [3,2,4], target = 6
Output: [1,2]

مثال ۳:

Input: nums = [3,3], target = 6
Output: [0,1]

محدودیت های مسئله رو هم باید در نظر بگیریم.

• تنها یک پاسخ معتبر وجود دارد.
• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109

حل مسئله

حالا که خوب مسئله رو خوندیم، بریم باهم حلش کنیم. پس ما یک ارایه داریم و برای بدست اوردن نتیجه باید ایندکس(ها) رو پیدا کنیم. همچنین میدونیم که ایندکس ارایه ها از صفر شروع میشه. سه روش برای حل این مسئله وجود دارد که با هم بررسی می کنیم.

روش اول - Brute Force

یکی از روش ها، روش brute force هست که میتونیم استفاده کنیم. بدین صورت، که برای همه جفت‌های ممکن از اعداد جستجو کنیم در واقع یکی یکی مقادیر آرایه رو جمع کنیم و با عدد تارگت مقایسه کنیم تا نتیجه بدست بیاد. اما این روش یک مشکلی داره، اونم اینکه پردازشش بسیار کند , پیچیدگی زمانی O(n2) است و این روش پیشنهاد نمیشه و بهترهه راه حل brute force را فقط برای صحت کامل بودن صورت مسئله امتحان کنید. با استفاده از راه حل های brute force است که می تونید بهینه سازی هایی را نیز ارائه دهید.

const twoSum = (nums, target) => {
for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) return [i, j];
        }
    }
};

برای بهبود این راه حل میتونیم حلقه for داخلی رو حذف کنیم و مقادیر رو داخل یک Object ذخیره کنیم. Object ها نمونه ای از یک Hash Table ها هستند که در ادامه به حل آن میپردازیم.

روش دوم - Two-pass Hash Table

ما اول اومدیم و ایندکس های آرایه ‍‍‍nums رو با forEach‍ داخل یک ابجکت indices که از قبل تعریف کرده بودیم، مقدار دهی کردیم و سپس در حلقه ی for ، عدد تارگت رو از مقدار عدد [index]nums‍‍ کم کردیم، عدد بدست اومده اسم شو complement گذاشتیم و اگر عدد بدست اومده داخل indices مون بود یعنی به جواب رسیدیم و داخل if هم که مسئله گفت بود دوبار یک المنت تکرار نشه و فیلتر کردیم.پیچیدگی زمانی این روش برابر با O(n) است.

var twoSum = function(nums, target) {
    const indices = {};

    nums.forEach((item, index) => {
       // 2 = 0
        indices[item] = index
    });

    for (let index = 0; index < nums.length; index++) {
        const complement = target - nums[index];

        if (indices[complement] !== undefined && indices[complement] !== index) {
            return [index, indices[complement]]
        }
    }
};

روش سوم - One-pass Hash Table

var twoSum = function(nums, target) {
    const indices = new Map();

    for (let index = 0; index < nums.length; index++) {
        const complement = target - nums[index];

        if (indices.has(complement)) {
            return [indices.get(complement), index]
        }

        indices.set(nums[index], index)
    }
};

امیدوارم که این مقاله رو دوست داشته باشید و حتما اگر در روش حل مسئله ایرادی می بینید یا پیشنهادی که باعث بهبود کیفیت مقاله هام میشه، حتما در کامنت ها برام بنویسید. ممنونم از وقتی که گذاشتید. :)