1. two sum حل المسئلة مع الشرح

يمكنك زيارة المسئلة في الموقع الرسمي leetcode من هنا

نص السؤال

إذا كانت المعطيات كالتالي:

• مصفوفة ==> nums
• رقم صحيح ==> target

المطلوب هو

• اوجد ال index الخاص بالرقمين في المصفوفة اللذان مجموعهما = target.

ملحوظات

• يوجد رقمين فقط مجموعهما ال target في المصفوفة
• لا يمكنك استخدام نفس العنصر مرتين
• لا يشترط الترتيب في الإجابة

مثال 1

• المعطيات: nums = [2,7,11,15] ، target = 9 .
• النتيجة: [0,1] .
• لماذا: لأن nums[0] + nums[1] = 9

مثال 2

• المعطيات: nums = [3,2,4] ، target = 6 .
• النتيجة: [1,2] .

مثال 3

• المعطيات: nums = [3,3] ، target = 6 .
• النتيجة: [0,1] .

شرح الحل

إذا أردت أن تحل هذه المسئلة وأردت إيجاد رقمين في المصفوفة يكون مجموعهما 9 فإنك ستقوم بتجربة كل رقمين مع بعضهما حتى تصل إلى رقمين في المصفوفة يكون ناتج جمعهم = 9 .

أي بصورة أخرى ستقوم بإستخدام متغيرين سيكونون لنا بمثابة ال pointers ولنفترض أنهما left , right.

وليبدأ left من اليسار أى left = 0 .

ويبدأ right بعده مباشرة أى right = 1 .

والفكرة هنا أننا سنقوم أول شئ بالتحقق هل مجموع العنصرين في left وفي right يساوي ال target لاحظ أن ال left و ال right هما ال indexes للعناصر في المصفوفة أى أنك ستتحقق من المعادلة nums[left] + nums[right] == target أم لا فإذا كانا متساويين فإننا سنقوم بعمل return للمصفوفة الجديدة [left,right] وإلا فإننا سنقوم بزيادة المتغير right بمقدار 1 ونتحقق مجدداً حتى يصل right إلى نهاية المصفوفة.

عندما يصل right إلى نهاية المصفوفة سنقوم بتزويده بمقدار 1 وسيصبح right متساوياً مع عدد عناصر المصفوفة أى أن right = 4 فإننا هنا يجب أن نتحقق إذا كان right يساوي عدد عناصر المصفوفة يجب أن نبدأ في الدورة التالية وهي أن نقوم بتزويد المؤشر left بمدار 1 وجعل المؤشر right بعده مباشرة.

لاحظ هنا أننا لا نحتاج أن نقارن ال 11 مع ال 15 لأننا قمنا بعمل هذه المقارنة في الدورة السابقة. إذاً هنا نحن نلاحظ أن كل العناصر قبل ال left قد تم التحقق منها واستبعادها وبالتالي لا يوجد داعي للتحقق منها مجدداً.

ستظل هذه العملية جارية حتى نجد أن العنصر left أصبح بينه وبين اخر عنصر خطوة واحدة

إذا قمنا بتزويد المؤشر left فسيصبح ال left = 3 ولكن المؤشر right ستكون قيمته 4 وهذا خارج الحدود الخاصة بالمصفوفة . وقد قمنا مسبقاً بفحص العنصر الأخير مع العنصر قبل الأخير حيث كانت ال left = 2 وال right = 3 . ونفهم من ذلك أننا سنتوقف حينما تصل left إلى العنصر الأخير والعنصر الأخير يكون ال index الخاص به هو عدد عناصر المصفوفة ناقص 1 (nums.length – 1) فيجب أن تكون ال left أصغر من هذه القيمة لاحظ في الكود.

function twoSum(nums: number[], target: number): number[] {
    let left = 0;
    let right = 1;
    while(left < nums.length - 1){
        if(nums[left] + nums[right] === target){
            return [left,right]
        }
        right++
        if(right == nums.length){
            left++
            right = left + 1
        }
    }
    return [-1,-1]
};

وأخيراً إذا لم تستطع الدالة أن تجد الحل ستعود ب [-1,-1] ولكن في هذه المسئلة دائماً يوجد جل.

Time Complexity

حل آخر

في الحل السابق كانت ال time complexity ليست أفضل شئ هنالك حل أفضل من حيث الوقت ولكن على حساب المساحة.

في هذه الطريقة نقوم باستخدام hash-map لتخزين العناصر وال index الخاص بها كالتالي.

سيكون ال key هو الرقم في المصفوفة وال value هو ال index الخاص به.

سنقوم بعمل loop واحدة في كل دورة يجب أن نخزن كل عنصر في ال map .

ثم نبحث في كل دورة في الmap عن عنصر إذا جمعناه مع العنصر الحالي يكون الناتج هو ال target وبالتالي تكون النتيجة [i , index of found number].

ملحوظة يجب أن نتحقق أولاً من وجود العنصر قبل إضافة العنصر الجديد لل map حتى لا نقوم بمقارنة العنصر مع نفسه.

ولكن كيف نتحقق فكر هنا معي على سبيل المثال نأخذ الأرقام في المثال السابق ونتتبع المسئلة:

لقد أضفت الرقم 11 إلى ال map وعلى وشك أن أضيف الرقم التالي وهو 15 فإنني قبل إضافته أتحقق هل 15 + رقم موجود مسبقاً يعطيني 9 (ال target): لا ، إذاً نقوم بإضافة ال 15 إلى ال map .

ثم في الدورة التالي نحن على وشك إضافة الرقم 2 فنتحقق هل يوجد رقم نضيفه ل 2 ليصبح الناتج 9 والإجابة هي الرقم 7 فنتحقق هل الرقم 7 موجود مسبقاً في ال map إذا مع كل رقم نحن نتحقق من وجود target – num[i] أو باختصار نتحقق من وجود الهدف – الرقم وإذا كان هذا الرقم موجود فقد وجدنا الحل وفي هذه المسئلة فإنها يوجد حل دائماً . نُكمل بإضافة الرقم 2 .

ثم نحن على وشك إضافة الرقم التالي وهو الرقم 7 فنتحقق هل يوجد الرقم (9 – 7) أى 2 في ال map مسبقاً والإجابة هي نعم يوجد فيكون الحل هو ال index الحالي وهو 3 وقيمة الرقم 2 في ال map وهو 2

أو بتعبير آخر [ i , map[ target – map[ i ] ] ]

function twoSum(nums: number[], target: number): number[] {
    let map: Record<number, number> = {};
    for (let i = 0; i < nums.length; i++) {
        if (map.hasOwnProperty(target - nums[i])) {
            return [i, map[target - nums[i]]]
        }
        map[nums[i]] = i;
    }

    return [-1, -1]
};

Time Complexity

Space Complexity