4Sum

Q: ما هو التعقيد الزمني لمسألة 4Sum؟

‏O(n³). تختار الحلقتان نحو n²/2 زوجًا (i, j) ، ويُجرى لكل زوج مسح واحد باستخدام مؤشرين، بحد أقصى n خطوة؛ ويُعدّ الفرز ‏O(n log n)‏ صغيرًا مقارنةً بذلك.

Q: كيف تُعمِّم مسألة 4Sum إلى kSum؟

اكتب kSum(nums, target, k) على قائمة مرتبة. عندما تكون k = 2، تنفّذ مسحًا بمؤشرين. وعندما تكون k أكبر، تكرّر المرور على القيمة الأولى، وتتخطّى القيم المكررة، وتستدعي نفسها باستخدام k-1 و target - nums[i] على القيم الواقعة إلى اليمين. يضيف كل مستوى عاملًا مقداره n، لذا تبلغ كلفة kSum مقدار O(n^(k-1)).

Q: هل يمكن حل مسألة 4Sum في زمن O(n²)؟

يمكنك تجميع مجاميع الأزواج البالغ عددها n²/2 في خريطة تجزئة، ومطابقة كل زوج مع الأزواج التي يساوي مجموعها target مطروحًا منه مجموع هذا الزوج. يكون ذلك سريعًا عندما يشترك عدد قليل من الأزواج في المجموع نفسه، لكن قد يحتوي أحد المجاميع على O(n²) زوجًا، لذا فإن الحالة الأسوأ ليست أفضل من O(n³).

متوسطمؤشران الترتيب

+10

تُعطى قائمة أعداد صحيحة nums وعدد صحيح target. أعد كل رباعية [a, b, c, d] تكون قيمها الأربع في مواضع مختلفة من nums ويكون مجموعها target. اكتب قيم كل رباعية بترتيب غير تنازلي. إذا أمكن اختيار القيم الأربع نفسها من مواضع مختلفة، فتظهر الرباعية مرة واحدة فقط. رتّب الإجابة حسب القيمة الأولى، ثم الثانية، ثم الثالثة. إذا لم تنطبق أي رباعية، فأعد قائمة فارغة.

الدالة

fourSum(nums: integer-array, target: integer) → integer-2d-array

numsinteger-array: الأرقام للاختيار منها، رقم واحد على الأقل
targetinteger: المجموع الذي يجب أن يبلغه كل رباعي
تُرجعinteger-2d-array: الرباعيات المتميزة التي يكون مجموعها target، وكل رباعية منها مرتبة، والقائمة مرتبة أيضًا؛ وقائمة فارغة إذا لم توجد أيٌّ منها

القيود

1 ≤ nums.length ≤ 200
-10⁸ ≤ nums[i] ≤ 10⁸
-10⁹ ≤ target ≤ 10⁹
يقع مجموع أي أربع قيم بين -4 × 10⁸ و4 × 10⁸، لذا فهو يتسع في عدد صحيح ذي 32 بت.
تُعَدّ الرباعيات التي تحتوي على القيم الأربع نفسها واحدةً.

أمثلة

المدخلات: nums = [3, -1, 0, 2, -2, 1, -3]target = 1
المخرجات: [[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]
الشرح: مجموع كل مجموعة من المجموعات الرباعية الأربع يساوي 1، على سبيل المثال -3 + (-1) + 2 + 3. تأتي أولًا المجموعتان اللتان تبدآن بـ -3، مرتبتين حسب قيمتهما الثانية: -1 قبل 0.

المدخلات: nums = [4, 4, 4, 4, 4, 4]target = 16
المخرجات: [[4, 4, 4, 4]]
الشرح: جميع الاختيارات الـ15 لأربعة مواضع من أصل ستة تعطي أربع قيم 4 مجموعها 16، لذا تظهر [4, 4, 4, 4] مرة واحدة.

المدخلات: nums = [1, 5, 2, 9]target = 3
المخرجات: []
الشرح: الخيار الوحيد هو الأرقام الأربعة كلها، و1 + 5 + 2 + 9 = 17، وليس 3، لذا فالإجابة قائمة فارغة.

سؤال إضافي

احسب عدد مجموعات المواضع الأربعة التي يكون مجموع قيمها مساويًا لـ target، بدلًا من عدد الرباعيات المختلفة. يحتوي المثال الثاني على 15 مجموعة. هل يمكنك فعل ذلك في O(n²)؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

يتطلب فحص كل مجموعة من أربعة مواضع كلفة O(n⁴)، وتؤدي القيم المكررة إلى إنشاء الرباعية نفسها مرات عديدة. طبّق اختزال 3Sum على مستوى أعمق: رتّب القيم، وثبّت أول قيمتين باستخدام حلقتين، واعثر على الزوج الأخير باستخدام مؤشرين، وتخطَّ القيم المكررة في كل مستوى.

جرّب كل مجموعة من أربعة

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

رتّب أولًا، بحيث تحتوي المواضع i < j < k < l على قيم بترتيب غير تنازلي، وتُكتب كل رباعية بالطريقة الصحيحة. تصل أربع حلقات متداخلة إلى كل اختيار لأربعة مواضع. لتجنّب التكرار، تنتقل الحلقة إلى الموضع التالي عندما يحتوي على القيمة نفسها التي جرّبتها في خطوة سابقة. عند وجود ست قيم 4، تجرّب كل حلقة موضعها الأول فقط، لذا تظهر [4, 4, 4, 4] مرة واحدة بدلًا من 15 مرة.

بالنسبة إلى 200 عدد، هناك 64,684,950 مجموعة من أربعة أعداد، ويزداد العدد بنحو 16 مرة عندما يتضاعف n.

الخوارزمية

رتّب nums.
أنشئ أربع حلقات متداخلة على i < j < k < l، تبدأ كل حلقة بعد حلقة المستوى المحيط بها بمقدار موضع واحد.
في كل حلقة، تخطَّ أي موضع ليس الأول في الحلقة وتكون قيمته مساوية لقيمة الموضع السابق.
سجّل [nums[i], nums[j], nums[k], nums[l]] عندما يكون مجموع القيم الأربع مساويًا لـ target. تنتجها الحلقات بترتيب تصاعدي.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # same second value as the round before
            for k in range(j + 1, n - 1):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                for l in range(k + 1, n):
                    if l > k + 1 and nums[l] == nums[l - 1]:
                        continue  # same fourth value as the round before
                    if nums[i] + nums[j] + nums[k] + nums[l] == target:
                        quads.append([nums[i], nums[j], nums[k], nums[l]])
    return quads

الترتيب، حلقتان، مؤشّران

الفكرة

ثبّت nums[i] وnums[j]، وما يتبقى هو مسألة إيجاد زوج: ابحث عن قيمتين على يمين j مجموعهما target - nums[i] - nums[j]. في قائمة مرتبة، تكفي عملية مسح واحدة للإجابة عنها. ابدأ بـlo عند j+1 وبـhi عند الفهرس الأخير. إذا كان المجموع أقل من target، حرّك lo إلى اليمين؛ وإذا كان أكبر منه، حرّك hi إلى اليسار.

كل حركة تستبعد قيمة لا تدخل في أي إجابة. إذا كان المجموع صغيرًا جدًا، فأكبر قيمة متبقية، وهي nums[hi]، لا تكفي مع nums[lo]، لذا يمكن استبعاد nums[lo]. أما المجموع الكبير جدًا فيستبعد nums[hi] للسبب المعاكس. يحتاج الزوج الواحد (i, j) إلى n حركات كحد أقصى، لذا تبلغ كلفة الأزواج n²/2 مقدار O(n³).

في المثال الأول، عندما يكون i عند -3 وj عند -1، يتحرك lo من 0 متجاوزًا 1 إلى 2، حيث -3 + (-1) + 2 + 3 = 1.

الخوارزمية

رتّب nums.
لكل i، تخطَّه عندما يكون i > 0 وتساوي nums[i] قيمة nums[i-1].
لكل j بعد i، تخطَّه عندما يكون j > i+1 وتساوي nums[j] قيمة nums[j-1].
عيّن lo = j+1 وhi = n-1. ما دام lo < hi، قارن مجموع القيم الأربع مع target: إذا كان أقل منه، حرّك lo إلى اليمين، وإذا كان أكبر منه، حرّك hi إلى اليسار.
عند العثور على تطابق، سجّل الرباعية، وحرّك المؤشرين، ثم زِد lo ما دامت قيمته تساوي القيمة التي استخدمها.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # this second value was already handled
            lo, hi = j + 1, n - 1
            while lo < hi:
                total = nums[i] + nums[j] + nums[lo] + nums[hi]
                if total < target:
                    lo += 1
                elif total > target:
                    hi -= 1
                else:
                    quads.append([nums[i], nums[j], nums[lo], nums[hi]])
                    lo += 1
                    hi -= 1
                    while lo < hi and nums[lo] == nums[lo - 1]:
                        lo += 1
    return quads

أخطاء شائعة وحالات حدّية

تجاوز j كلما كانت nums[j] تساوي nums[j-1]. عند j = i+1، يقارن ذلك بالقيمة التي يستخدمها i، لذا فإن [2, 2, 2, 2, 2] مع الهدف 8 تفقد [2, 2, 2, 2].
نسخ شرط الإنهاء المبكر من 3Sum، nums[i] > target. مع [-5, -4, -3, -2, -1] والهدف -10، تتوقف الحلقة عند -5 وتفوّت [-4, -3, -2, -1].
القوائم التي يقل طولها عن أربعة. مع رقم واحد أو رقمين، تكون n-3 سالبة: يؤدي 0..<(n - 3) إلى توقف التنفيذ بخطأ في Swift، كما أن n - 3 على usize في Rust يؤدي إلى تجاوز سفلي. أعد قائمة فارغة أولًا.
جمع الرباعيات في مجموعة تجزئة وإرجاعها دون ترتيب.

أسئلة شائعة3

ما هو التعقيد الزمني لمسألة 4Sum؟

‏O(n³). تختار الحلقتان نحو n²/2 زوجًا (i, j)، ويُجرى لكل زوج مسح واحد باستخدام مؤشرين، بحد أقصى n خطوة؛ ويُعدّ الفرز ‏O(n log n)‏ صغيرًا مقارنةً بذلك.

كيف تُعمِّم مسألة 4Sum إلى kSum؟

اكتب kSum(nums, target, k) على قائمة مرتبة. عندما تكون k = 2، تنفّذ مسحًا بمؤشرين. وعندما تكون k أكبر، تكرّر المرور على القيمة الأولى، وتتخطّى القيم المكررة، وتستدعي نفسها باستخدام k-1 وtarget - nums[i] على القيم الواقعة إلى اليمين. يضيف كل مستوى عاملًا مقداره n، لذا تبلغ كلفة kSum مقدار O(n^(k-1)).

هل يمكن حل مسألة 4Sum في زمن O(n²)؟

يمكنك تجميع مجاميع الأزواج البالغ عددها n²/2 في خريطة تجزئة، ومطابقة كل زوج مع الأزواج التي يساوي مجموعها target مطروحًا منه مجموع هذا الزوج. يكون ذلك سريعًا عندما يشترك عدد قليل من الأزواج في المجموع نفسه، لكن قد يحتوي أحد المجاميع على O(n²) زوجًا، لذا فإن الحالة الأسوأ ليست أفضل من O(n³).

def fourSum(nums, target):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

الوسائط

nums = [3, -1, 0, 2, -2, 1, -3]
target = 1

الإخراج المتوقع

[[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]