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

تقنية المؤشّرين

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

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

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

الخطوة 1 من 11
1function twoSum(nums, target) {2  let lo = 0, hi = nums.length - 1;3  while (lo < hi) {4    const sum = nums[lo] + nums[hi];5    if (sum === target) return [lo, hi];6    if (sum < target) lo++;7    else hi--;8  }9  return null;10}
target
= 10
  1. 1lo
  2. 3
  3. 4
  4. 6
  5. 8
  6. 11hi

المصفوفة مرتّبة. يبدأ lo من الطرف الأيسر، ويبدأ hi من الطرف الأيمن.

كيف تعمل

ضع مؤشّراً عند كل طرف من طرفي المصفوفة المرتّبة. إذا كان المجموع صغيراً جداً فحرّك المؤشّر الأيسر إلى اليمين، وإذا كان كبيراً جداً فحرّك المؤشّر الأيمن إلى اليسار. كل حركة تستبعد مجموعة كاملة من الأزواج، لذلك يستغرق البحث زمناً خطّياً بدلاً من فحص كل زوج.