العثور على زوج ذي مجموع محدد
التفوق على القوة الغاشمة O(n^2)
العثور على زوج ذي مجموع محدد درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 2 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
مسألة مجموع الزوج
لديك مصفوفة وهدف، وعليك إيجاد قيمتين يصل مجموعهما إلى الهدف. وهذه من أكثر مسائل الإحماء شيوعًا في المسابقات. 🔍
طريقة القوة الغاشمة
تحاول الطريقة الواضحة فحص كل زوج باستخدام حلقتين متداخلتين. وهي تنجح، لكن فحص جميع الأزواج يتطلب O(n^2) وقد يكون بطيئًا جدًا.
for i in range(n):
for j in range(i + 1, n):
if a[i] + a[j] == target:
return (i, j)متى تفشل القوة الغاشمة
عندما تقترب قيمة n من 100000، يصبح O(n^2) عشرة مليارات عملية فحص، وستواجه TLE. وهذه القيود تشير إلى ضرورة إيجاد طريقة أسرع.
رتّب ثم امسح
إذا رتّبت المصفوفة أولًا، فسيحلّها مؤشّران من الطرفين في مرور واحد. يستغرق الترتيب O(n log n)، ثم يستغرق المسح O(n).
a.sort()
left, right = 0, len(a) - 1قارن بالهدف
في كل خطوة، اقرأ a[left] + a[right]. فهذا الرقم الواحد يحدد حركتك التالية من دون أي تخمين.
total = a[left] + a[right]تطابق تام: انتهى الأمر
إذا ساوى المجموع الهدف، فقد عثرت على الزوج. أعده فورًا لأنك تحتاج إلى إجابة صحيحة واحدة فقط.
if total == target:
return (left, right)وإلا فعدّل
إذا كان المجموع صغيرًا جدًا، فحرّك left إلى اليمين؛ وإذا كان كبيرًا جدًا، فحرّك right إلى اليسار. ويضمن الترتيب أن تساعد كل حركة.
elif total < target:
left += 1
else:
right -= 1لا يوجد زوج
إذا تجاوز المؤشران بعضهما من دون تطابق، فلا يوجد زوج صحيح. ويكون انتهاء الحلقة إجابة مكتملة بحد ذاته.
بديل مجموعة التجزئة
إذا كان عليك الاحتفاظ بالفهارس الأصلية، فستكون مجموعة التجزئة أوضح: افحص لكل قيمة ما إذا كان الهدف مطروحًا منها قد ظهر من قبل.
seen = set()
for x in a:
if target - x in seen:
# found
pass
seen.add(x)اختر طريقتك
استخدم المؤشرين عندما تكون المصفوفة مرتبة أو يمكن ترتيبها؛ واستخدم مجموعة التجزئة عندما تحتاج إلى O(n) فعلًا من دون ترتيب أو عندما يجب الاحتفاظ بالفهارس.
انتبه إلى التكرارات
إذا كان بإمكان قيمة أن تقترن بنفسها، فتأكد من اختلاف الفهرسين. ويمنع فحص سريع مثل left != right أو i != j هذا الخطأ.
تحقّق سريع
تريد التفوق على القوة الغاشمة ذات التعقيد O(n^2) لإيجاد زوج يساوي مجموعُه هدفًا.
مراجعة
رتّب المصفوفة ثم امسحها باستخدام مؤشرين لإيجاد الزوج المستهدف في O(n log n)، أو استخدم مجموعة تجزئة بتعقيد O(n) عندما تكون الفهارس مهمة. اختر وفقًا للقيود. ✅
الأسئلة الشائعة
هل درس «العثور على زوج ذي مجموع محدد» مجاني؟
نعم — نص درس «العثور على زوج ذي مجموع محدد» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «العثور على زوج ذي مجموع محدد»؟
التفوق على القوة الغاشمة O(n^2) تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 2 من أصل 4.
كم من الوقت يستغرق درس «العثور على زوج ذي مجموع محدد»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- مؤشران في مصفوفة مرتبة
- العثور على زوج ذي مجموع محدد
- إزالة التكرارات في مكانها
- دمج تسلسلين مرتبين