Two Sum
لديك مصفوفة من الأعداد الصحيحة nums وعدد صحيح target. مجموع عنصرين بالضبط من nums، في موضعين مختلفين، يساوي target. أعد فهرسي هذين العنصرين، مع وضع الفهرس الأصغر أولًا.
الدالة
- numsinteger-array
- مصفوفة الأعداد الصحيحة المراد البحث فيها
- targetinteger
- يجب أن يصل مجموع المدخلين إلى
- تُرجعinteger-array
- المؤشران، مع وضع الأصغر أولًا
القيود
2 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109-109 ≤ target ≤ 109- يوجد زوج واحد بالضبط من المواضع المختلفة مجموعهما يساوي
target.
أمثلة
- المدخلات
- nums = [3, 8, 12, 5]target = 17
- المخرجات
- [2, 3]
- الشرح
- يوجد 12 عند الفهرس 2 و5 عند الفهرس 3، و12 + 5 = 17. لا يصل أي زوج آخر إلى 17.
- المدخلات
- nums = [6, 1, 4, 10]target = 7
- المخرجات
- [0, 1]
- الشرح
- 6 عند الفهرس 0 و1 عند الفهرس 1 مجموعهما 7: يمكن أن يكون هذا الزوج أول عنصرين.
- المدخلات
- nums = [2, -6, 9, 4, 13]target = 3
- المخرجات
- [1, 2]
- الشرح
- -6 عند الفهرس 1 و9 عند الفهرس 2 مجموعهما 3. تتزاوج الأعداد السالبة بالطريقة نفسها التي تتزاوج بها الأعداد الموجبة.
سؤال إضافي
إذا كانت nums مرتبة مسبقًا، فهل يمكنك إيجاد الزوج في زمن O(n) باستخدام ذاكرة إضافية لا تتجاوز O(1)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
تجربة كل زوج باستخدام حلقتين متداخلتين صحيحة، لكن مع 10,000 رقم، يعني ذلك نحو 50 مليون عملية تحقق. هل يمكنك العثور على الرقم المقابل لكل رقم دون فحص القائمة مرة أخرى؟
عندما تقف عند قيمة
x، فأنت تعرف بالفعل القيمة التي تُكمل الزوج: الهدف ناقصx. والسؤال الوحيد هو ما إذا كنت قد مررت بهذه القيمة من قبل، وعند أي فهرس.مرّ على القائمة مرة واحدة واحتفظ بخريطة تجزئة تربط كل قيمة تجاوزتها بفهرسها. عند كل موضع، ابحث أولًا عن القيمة المكملة؛ إذا كانت في الخريطة، فسيكون لديك الفهرسان. وإلا، فخزّن القيمة الحالية وتابع. البحث قبل التخزين هو ما يمنع العدد من الاقتران بنفسه.
الحل
فحص كل زوج ينجح، لكن مقدار العمل يزداد بمربع الطول. اقلب السؤال: عندما تكون عند العدد x، فأنت تعرف مسبقًا أن العدد المقابل له يجب أن يكون target - x. تخبرك خريطة التجزئة في زمن ثابت ما إذا كنت قد مررت بهذه القيمة، لذا تكفي عملية مرور واحدة.
تحقّق من كل زوج
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
ثبّت فهرسًا أول i وجرّب كل فهرس j يقع إلى يمينه إلى أن يصبح nums[i] + nums[j] مساويًا لـ target. بدء j من i + 1 يمنع الفهرس من الاقتران بنفسه، ويجرّب كل زوج مرة واحدة، ويضع الفهرس الأصغر أولًا. الزوج الذي تريده هو أحد الأزواج التي تجرّبها، لذا ستجده.
تشكّل n أعداد نحو n²/2 زوجًا: عندما تكون n = 10^4، فهذا يعني قرابة 5 × 10^7 عملية جمع.
الخوارزمية
- كرّر
iعلى كل فهرس فيnums. - لكل قيمة من
i، كرّرjمنi + 1حتى آخر فهرس. - إذا كان
nums[i] + nums[j]يساويtarget، فأعِد[i, j]. - إذا انتهت الحلقتان، فأعِد مصفوفة فارغة. تضمن المسألة أن هذا لن يحدث أبدًا.
def twoSum(nums, target):
n = len(nums)
for i in range(n):
# Only look at partners to the right, so each pair is checked once.
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []مرور واحد باستخدام خريطة تجزئة
الفكرة
بالنسبة إلى nums[i] ثابتة، تبحث الحلقة الداخلية في أسلوب القوة الغاشمة عن قيمة تعرفها مسبقًا: target - nums[i]. هذا المسح هو في الحقيقة عملية بحث، وتتيح خريطة تجزئة تربط القيمة بالفهرس إجراء عمليات البحث في زمن ثابت بالمتوسط.
ابحث أولًا، ثم خزّن. عندها لا يمكن للعدد أن يقترن إلا بعدد يسبقه، وليس بنفسه، وبما أن العدد المقابل يأتي دائمًا قبله، فإن فهرسه يأتي أولًا. تتم زيارة كل عدد مرة واحدة مع عمليات على الخريطة بزمن ثابت، لذا يكون البحث O(n)؛ والثمن هو خريطة تضم ما يصل إلى n من الإدخالات.
الخوارزمية
- أنشئ خريطة فارغة من القيم إلى الفهارس.
- لكل فهرس
i، احسبneed، وهي القيمة التي تُكمل الزوج:targetناقصnums[i]. - إذا كانت
needفي الخريطة، فأعِد الفهرس المخزّن لها متبوعًا بـi. - وإلا، فخزّن
nums[i]مع الفهرسiوتابع.
def twoSum(nums, target):
seen = {}
for i, num in enumerate(nums):
need = target - num
if need in seen:
return [seen[need], i]
seen[num] = i
return []
أخطاء شائعة وحالات حدّية
- تخزين رقم قبل البحث عن الرقم المكمل له. مع
[4, 2, 6]وtarget = 8، يجد الرقم 4 نفسه وتُرجع[0, 0]. - إرجاع الفهارس بترتيب خاطئ. عند البحث قبل التخزين، يكون الفهرس الموجود في الخريطة هو الأصغر، لذا يأتي أولًا.
- ترتيب المصفوفة لاستخدام مؤشرين، ثم إرجاع المواضع في النسخة المرتبة. احتفظ بالفهرس الأصلي لكل قيمة بجانبها.
- افتراض أن القيم موجبة أو متميزة. في
[0, 7, -3, 0]معtarget = 0، يشكّل الصفران زوجًا:[0, 3]. - في Lua وR، إرجاع الفهارس التي تبدأ من 1. اطرح 1 من كل فهرس.
أسئلة شائعة3
ما هو التعقيد الزمني لمسألة Two Sum؟
يعمل حل خريطة التجزئة في زمن O(n)، لأنه يمرّ على كل عدد مرة واحدة، ويستغرق كل بحث أو إدراج زمنًا ثابتًا في المتوسط. ويستخدم مساحة إضافية قدرها O(n) للخريطة. أما التحقق من كل زوج فيستغرق زمنًا قدره O(n²) ومساحة قدرها O(1).
هل يمكن حل مسألة Two Sum دون استخدام مساحة إضافية؟
ليس في زمن خطي على مصفوفة غير مرتبة. مع مساحة إضافية O(1)، ستعود إلى فحص كل زوج، وهذا يتطلب O(n²). تستبدل خريطة التجزئة ذلك بذاكرة O(n) مقابل الزمن الخطي.
كيف يتعامل Two Sum مع الأرقام المكررة؟
تعمل القيم المكررة عندما تبحث عن الرقم المكمل قبل تخزين الرقم الحالي. في [7, 3, 7] مع target = 14، يُخزَّن الرقم 7 الأول عند الفهرس 0، ويعثر عليه الرقم 7 الثاني، فتكون النتيجة [0, 2]. لا يقترن الرقم 7 المنفرد بنفسه أبدًا: فهو لم يُضف إلى الخريطة بعد عند البحث عنه.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def twoSum(nums, target):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
nums = [3, 8, 12, 5] target = 17
الإخراج المتوقع
[2, 3]