Two Sum
تحصل على قائمة من الأعداد الكلية وقيمة مستهدفة. مجموع عددين بالضبط من القائمة يساوي القيمة المستهدفة، ومهمتك هي تحديد موضعيهما.
خذ nums = [3, 8, 12, 5] وtarget = 17. تقع القيمة 12 عند الفهرس 2، وتقع القيمة 5 عند الفهرس 3، و12 + 5 = 17، لذا تكون الإجابة [2, 3].
يجب أن يأتي العددان من موضعين مختلفين. في [4, 2, 6] مع target = 8، لا يُسمح باستخدام العدد 4 مرتين؛ والإجابة هي [1, 2] لأن 2 + 6 = 8. ومع ذلك، يمكن أن تظهر القيمة نفسها مرتين: ففي [7, 3, 7] مع target = 14، تكون الإجابة [0, 2].
اكتب دالة باسم twoSum تستقبل مصفوفة من الأعداد الصحيحة nums وعددًا صحيحًا target، وتُرجع مصفوفة تحتوي على فهرسين [i, j] بحيث يساوي nums[i] + nums[j] القيمة target.
يجب أن يشير الفهرسان إلى موضعين مختلفين، وأن يُعادا بترتيب تصاعدي (i أصغر من j). لكل مُدخل زوج واحد فقط يحقق ذلك.
القيود: 2 ≤ nums.length ≤ 10^4، -10^9 ≤ nums[i] ≤ 10^9، -10^9 ≤ target ≤ 10^9.
الدالة
- arg1integer-array
- arg2integer
- تُرجعinteger-array
أمثلة
- المدخلات
- arg1 = [3, 8, 12, 5]arg2 = 17
- المخرجات
- [2, 3]
- المدخلات
- arg1 = [6, 1, 4, 10]arg2 = 7
- المخرجات
- [0, 1]
- المدخلات
- arg1 = [2, -6, 9, 4, 13]arg2 = 3
- المخرجات
- [1, 2]
+13 اختبارات مخفية عند الإرسال
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
تجربة كل زوج باستخدام حلقتين متداخلتين صحيحة، لكن مع 10,000 رقم، يعني ذلك نحو 50 مليون عملية تحقق. هل يمكنك إيجاد الرقم المقابل لكل رقم دون فحص القائمة مرة أخرى؟
عندما تقف عند القيمة
x، فأنت تعرف بالفعل القيمة التي ستُكمل الزوج: الهدف ناقصx. والسؤال الوحيد هو ما إذا كنت قد مررت بتلك القيمة من قبل، وعند أي فهرس.امشِ على القائمة مرة واحدة واحتفظ بخريطة تجزئة تربط كل قيمة مررت بها بفهرسها. في كل موضع، ابحث أولًا عن القيمة المكملة المفقودة؛ فإذا كانت في الخريطة، يكون لديك الفهرسان. وإلا، فخزّن القيمة الحالية وانتقل إلى التالي. البحث قبل التخزين هو ما يمنع العدد من الاقتران بنفسه.
شرح كامل لهذه المسألة قادم قريبًا.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def twoSum(nums, target):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
arg1 = [3, 8, 12, 5] arg2 = 17
المتوقع
[2, 3]