Two Sum II: Sorted Input
لديك مصفوفة من الأعداد الصحيحة numbers مرتبة بترتيب غير تنازلي، وعدد صحيح target. يوجد زوج واحد بالضبط من موضعين مختلفين يحتوي على قيمتين مجموعهما يساوي target. أعد هذين الموضعين على هيئة فهارس تبدأ من 0، مع وضع الفهرس الأصغر أولًا.
الدالة
- numbersinteger-array
- المصفوفة المرتبة من الأعداد الصحيحة
- targetinteger
- المجموع الذي يجب أن تبلغه القيمتان
- تُرجعinteger-array
- الفهرسان المعتمدان على الصفر [i, j] حيث i < j و numbers[i] + numbers[j] == target
القيود
2 ≤ numbers.length ≤ 104-5 × 108 ≤ numbers[i] ≤ 5 × 108-109 ≤ target ≤ 109numbersمرتبة بترتيب غير تنازلي.- يوجد زوج واحد فقط من الفهارس
i < jبحيث يكونnumbers[i] + numbers[j] == target.
أمثلة
- المدخلات
- numbers = [-4, 1, 3, 8, 12]target = 9
- المخرجات
- [1, 3]
- الشرح
- يقع 1 عند الفهرس 1 و8 عند الفهرس 3، و1 + 8 = 9. لا يصل أي زوج آخر إلى 9: على سبيل المثال، -4 + 12 = 8.
- المدخلات
- numbers = [2, 2, 5, 7]target = 4
- المخرجات
- [0, 1]
- الشرح
- الرقمان 2 عند الفهرسين 0 و1 يقعان في موضعين مختلفين، لذا يمكن أن يشكّلا الزوج: 2 + 2 = 4.
- المدخلات
- numbers = [-10, -3, 0, 6]target = -4
- المخرجات
- [0, 3]
- الشرح
- -10 عند الفهرس 0 و6 عند الفهرس 3 يعطيان -10 + 6 = -4. يمكن أن تشمل الإجابة المصفوفة بأكملها.
+13 اختبارات مخفية عند الإرسال
سؤال إضافي
هل يمكنك حلّها في زمن O(n) وباستخدام ذاكرة إضافية O(1)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
المصفوفة مرتبة. انظر إلى أصغر قيمة وأكبر قيمة معًا. ماذا يخبرك مجموعهما عندما يكون أقل من
target؟إذا كان مجموع القيمة الأولى والقيمة الأخيرة صغيرًا جدًا، فالقيمة الأولى صغيرة جدًا مع كل قيمة أخرى، لأن القيمة الأخيرة هي الأكبر بالفعل. يمكنك استبعادها.
أبقِ مؤشرًا عند كل طرف. عندما يكون المجموع صغيرًا جدًا، حرّك المؤشر الأيسر إلى اليمين؛ وعندما يكون كبيرًا جدًا، حرّك المؤشر الأيمن إلى اليسار. توقّف عندما يساوي المجموع
target.
الحل
تحل خريطة التجزئة النسخة غير المرتبة بتمريرة واحدة، لكنها تستهلك ذاكرة بحجم O(n). المصفوفة هنا مرتبة، وهذا الترتيب يخبرك بأي اتجاه تتحرك. ضع مؤشرًا عند كل طرف. إذا كان المجموع صغيرًا جدًا، فلن يساعد إلا اختيار قيمة أكبر من اليسار؛ وإذا كان كبيرًا جدًا، فلن تساعد إلا قيمة أصغر من اليمين. تستبعد كل خطوة قيمة واحدة نهائيًا، لذا تكفي تمريرة واحدة للعثور على الزوج دون ذاكرة إضافية.
تحقّق من كل زوج
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
جرّب كل زوج من المواضع i < j واختبر ما إذا كان numbers[i] + numbers[j] يساوي target. بما أن i يتحرك من اليسار ويبدأ j من الموضع الذي يليه مباشرةً، فإن أول زوج تعثر عليه يكون فيه الفهرس الأصغر أولًا.
هذا صحيح، لكنه يتجاهل الترتيب المصنّف. عندما يكون n = 10^4، يوجد نحو 5 × 10^7 زوجًا، وعندما تكون الإجابة قرب نهاية المصفوفة، ستختبر جميعها تقريبًا. وهذا بطيء جدًا للاختبارات الكبيرة.
الخوارزمية
- كرّر الحلقة على
iعبر كل فهرس. - كرّر الحلقة على
jمنi+1إلى الفهرس الأخير. - إذا كان
numbers[i] + numbers[j]يساويtarget، فأعِد[i, j].
def twoSumSorted(numbers, target):
n = len(numbers)
for i in range(n):
for j in range(i + 1, n):
if numbers[i] + numbers[j] == target:
return [i, j]
return []البحث الثنائي عن كل شريك
الفكرة
بمجرد أن تثبّت القيمة الأولى numbers[i]، ستعرف القيمة المقابلة لها بدقة: target - numbers[i]. الجزء من المصفوفة الواقع إلى يمين i مرتب، لذا يمكن للبحث الثنائي أن يحدد خلال O(log n) خطوة ما إذا كانت تلك القيمة موجودة فيه.
بالنسبة إلى [-4, 1, 3, 8, 12] وtarget = 9: عند i = 0، ستكون القيمة المقابلة 13، لكنها غير موجودة. وعند i = 1، تكون القيمة المقابلة 8، ويعثر البحث عليها عند الفهرس 3. الإجابة هي [1, 3].
البحث فقط إلى يمين i يُبقي الفهرس الأصغر أولًا ويمنع القيمة من الاقتران بنفسها. الزوج فريد، لذا تظهر القيمة المقابلة مرة واحدة على الأكثر في ذلك النطاق، وأي تطابق هو الإجابة. إجمالًا: n عمليات بحث، يستغرق كل منها O(log n).
الخوارزمية
- كرّر
iمن 0 إلىn-2. - احسب
need = target - numbers[i]. - ابحث ثنائيًا عن
needضمن الفهارس منi+1إلىn-1. - إذا وجدته عند
mid، فأعِد[i, mid].
def twoSumSorted(numbers, target):
n = len(numbers)
for i in range(n - 1):
need = target - numbers[i]
lo, hi = i + 1, n - 1
while lo <= hi:
mid = (lo + hi) // 2
if numbers[mid] == need:
return [i, mid]
if numbers[mid] < need:
lo = mid + 1
else:
hi = mid - 1
return []مؤشران من الطرفين
الفكرة
ابدأ بـ left = 0 وright = n-1 وانظر إلى numbers[left] + numbers[right]. إذا كان الناتج يساوي target، فقد انتهيت. إذا كان أصغر من المطلوب، فلا يمكن أن تكون numbers[left] جزءًا من الإجابة: فحتى عند جمعها مع أكبر قيمة ما زالت قيد النظر، لن تبلغ المجموع المطلوب. لذا حرّك left إلى اليمين. وإذا كان المجموع أكبر من المطلوب، فلا يمكن أن تكون numbers[right] جزءًا منه أيضًا، لأن حتى أصغر قيمة متبقية ستجعل المجموع يتجاوز المطلوب. لذا حرّك right إلى اليسار.
في كل حركة، تستبعد قيمة واحدة يستحيل أن تكون ضمن الزوج، بينما لا يُستبعد الزوج نفسه أبدًا. يلتقي المؤشران بعد n-1 حركة على الأكثر، لذا يكون المسح بتعقيد O(n) ويستخدم متغيرين.
في [-4, 1, 3, 8, 12] عندما تكون target = 9: -4 + 12 = 8 أصغر من المطلوب، لذا ينتقل left إلى الفهرس 1. ثم 1 + 12 = 13 أكبر من المطلوب، لذا ينتقل right إلى الفهرس 3. والآن 1 + 8 = 9، والإجابة هي [1, 3].
الخوارزمية
- عيّن
leftإلى 0 وrightإلىn-1. - ما دام
left < right، احسبtotal = numbers[left] + numbers[right]. - إذا كان
totalيساويtarget، فأعِد[left, right]. - إذا كان
totalأصغر، فأضف 1 إلىleft؛ وإذا كان أكبر، فاطرح 1 منright.
def twoSumSorted(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left, right]
if total < target:
left += 1 # need a bigger sum
else:
right -= 1 # need a smaller sum
return []
أخطاء شائعة وحالات حدّية
حلقة المؤشرين قصيرة، لذا تختبئ الأخطاء في التفاصيل المحيطة بها.
- إرجاع مواضع تبدأ من 1. هذه النسخة تتطلب فهارس تبدأ من 0: بالنسبة إلى
[-4, 1, 3, 8, 12]وtarget = 9، تكون الإجابة[1, 3]، لا[2, 4]. في Lua وR، اطرح 1 قبل الإرجاع. - التكرار باستخدام
left <= right. عندما يلتقي المؤشران، سيستخدم المجموع القيمة نفسها مرتين. - تحريك المؤشر الخطأ. المجموع الأصغر من المطلوب يحتاج إلى قيمة أكبر، والمؤشر
leftوحده يمكنه توفيرها. - رفض القيم المكررة. تستخدم
[2, 2, 5, 7]معtarget = 4كلا القيمتين 2، وهما في موضعين مختلفين. - تجاوز السعة. تضمن الحدود هنا أن يبقى كل مجموع ضمن نطاق عدد صحيح ذي 32 بت. إذا كان من الممكن أن تصل القيم إلى
10^9، فاجمعها باستخدام نوع ذي 64 بت.
أسئلة شائعة4
لماذا تنجح مؤشّران في مسألة مجموع عددين على مصفوفة مرتبة؟
عندما يكون مجموع الطرفين صغيرًا جدًا، تكون القيمة اليسرى صغيرة جدًا مع كل قيمة مقابلة ما زالت ضمن الاحتمالات، لأن الطرف الأيمن هو الأكبر بينها. يمكنك استبعادها نهائيًا. وينطبق الاستدلال نفسه على استبعاد القيمة اليمنى عندما يكون المجموع كبيرًا جدًا. لا يُستبعد زوج الإجابة أبدًا، لذا ينتهي المؤشران عنده.
ما التعقيد الزمني لمسألة Two Sum II؟
يعمل حل المؤشرين في زمن O(n) وبمساحة إضافية O(1): في كل خطوة، يتحرك أحد المؤشرين إلى الداخل، ويلتقيان بعد n-1 خطوة على الأكثر. يستغرق البحث الثنائي عن كل عنصر شريك O(n log n)، بينما يستغرق التحقق من كل زوج O(n²).
لماذا لا نستخدم جدول تجزئة كما في مسألة مجموع عددين الأولى؟
تعمل خريطة التجزئة أيضًا بزمن O(n)، لكنها تخزّن ما يصل إلى n من القيم. يجعل الترتيب التصاعدي هذه الذاكرة غير ضرورية: إذ يعرف المؤشران أي اتجاه يسلكان اعتمادًا على المجموع وحده. يطرح المحاورون هذه الصيغة لمعرفة ما إذا كنت تستفيد من الترتيب المعطى لك.
متى يكون البحث الثنائي الخيار الأفضل هنا؟
عندما تكون إحدى القيمتين ثابتة ولا تحتاج إلا إلى إيجاد القيمة المقابلة لها. إذا كان لا بد أن تكون numbers[0] ضمن الزوج، فإن بحثًا ثنائيًا واحدًا يعثر على الفهرس الآخر في O(log n). ولإيجاد زوج غير معروف، يكون المسح باستخدام مؤشرين أسرع من إجراء n عمليات بحث منفصلة.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def twoSumSorted(numbers, target):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
numbers = [-4, 1, 3, 8, 12] target = 9
المتوقع
[1, 3]