ENDEAR
ابدأ مجاناً
خوارزميةمجاني

مجموع عددين باستخدام جدول تجزئة

اعثر على عددين مجموعهما يساوي الهدف في مرور واحد، حتى في مصفوفة غير مرتّبة.

الزمن
O(n)
الذاكرة
O(n)

تتبّعها خطوة بخطوة

الخطوة 1 من 9
1function twoSum(nums, target) {2  const seen = new Map();3  for (let i = 0; i < nums.length; i++) {4    const need = target - nums[i];5    if (seen.has(need)) return [seen.get(need), i];6    seen.set(nums[i], i);7  }8  return null;9}
target
= 9
  1. 3
  2. 8
  3. 2
  4. 7
  5. 5
seenفارغ

نبدأ بجدول فارغ seen، سيحفظ كل عدد مع فهرسه.

كيف تعمل

لكل عدد، احسب العدد المكمّل الذي يحتاجه ليصل إلى الهدف، ثم اسأل جدول التجزئة هل ظهر هذا المكمّل من قبل. البحث في الجدول يكلّف O(1) في المتوسط، لذا يكفي مرور واحد: الزمن O(n). والثمن هو الذاكرة: قد يحتفظ الجدول بما يصل إلى n عدداً، فالذاكرة O(n). مقايضة الذاكرة بالزمن بهذه الطريقة من أكثر الحيل شيوعاً في المسائل البرمجية.

تدرّب على اكتشاف هذا النمط →