3Sum لماذا لا يعمل حل O(nlogn) هذا؟

Question

لقد كنت أستخدم LeetCode وقمت بمعالجة مشكلة 3Sum وحاولت أولاً القيام بحل O(nlogn) وبعد رؤية الحل المقترح أرى أن الحل هو $O(ن^2)$ أو $O(n^2 imes \log n)$ وليس هذا فحسب، بل إن المشكلة هي موضوع تم بحثه بشكل كبير، لذا لا أعتقد أنني وجدت حلاً أفضل ولكن لا يمكنني معرفة سبب عدم نجاح النهج الذي أتبعه، ويمكنني استخدام المساعدة لمعرفة ذلك.

المشكلة هي ما يلي
العثور على ثلاثة أرقام في مجموعة من هذا القبيل $أ + ب + ج = ر$,
ال مشكلة في ليت كود يختلف قليلاً حيث تحتاج إلى العثور على أقرب مبلغ.

الكود الخاص بي هو التالي:

1. فرز المصفوفة.
2.   ابدأ بمؤشرين i=0 و j= last element of array
3.     استخدم البحث الثنائي بين i و j لايجاد m مثل ذلك arr[m] == target - arr[i] - arr[j], ، إذا كان هذا m لا يوجد عودة m مثل ذلك arr[m] هو الأقرب.
4.     لو arr[i] + arr[m] + arr[j] == target ثم الانتهاء الخاص بك.
5.     وإلا إذا arr[i] + arr[m] + arr[j] < target ثم أضف 1 إلى i آخر طرح 1 النموذج j.
6. كرر 3 → 5 حتى j - i == 2
7. إرجاع أفضل ما تم العثور عليه i,m,j

المنطق في الخطوة 5 هو أنه إذا كان الحل الذي تم العثور عليه أقل من الهدف، فيجب علينا زيادته i بحيث يكون تخميننا التالي أكبر.

شفرة:

def binSearch(arr, s, e, t):
    m = (s + e) // 2
    r = m
    d = 9999
    while s <= e:
        m = (s + e) // 2
        if arr[m] == t:
            return m
        elif arr[m] > t:
            e = m - 1
        else:
            s = m + 1

        if d > abs(t - arr[m]):
            d = abs(t - arr[m])
            r = m
    return r


class Solution:
    def threeSumClosest(self, nums, target: int) -> int:
        nums.sort()

        s = 0
        e = len(nums) - 1
        minn = 999999
        t = ()
        while e - s >= 2:
            left = nums[s]
            right = nums[e]
            remaining = target - (left + right)
            m = binSearch(nums, s + 1, e - 1, remaining)
            middle = nums[m]
            r = left + middle + right

            # print("i's: ", (s,m,e))
            # print("values: ", (nums[s], nums[m], nums[e]))
            # print("r", r)
            # print("**************")

            if r == target:
                return r
            elif r < target:
                s += 1
            else:
                e -= 1

            if abs(target - r) < minn:
                minn = abs(target - r)
                t = r
        return t

Answer 1

يفشل هذا، على سبيل المثال، [1، 9، 55، 55، 100]، t=111.يجد التكرار الأول 110 ويزيد i لاستبعاد 1 كاحتمال، ولكن الحل الوحيد، [1، 55، 55]، يحتاج إلى 1.

المشكلة الأساسية هي أنه عند زيادة i أو تقليل j، فإنك تفترض أن العنصر الذي تقدمت به للتو ليس ضروريًا - وأن هناك بعض الحلول التي لا تتضمنه.لكن هذا لا يبرره أي شيء، ومن الممكن أن تكون كل الحلول بحاجة إلى هذا العنصر.

إحدى الطرق الرائعة لاختبار أفكار الخوارزمية مثل هذه هي كتابة برنامج صغير يولد العديد من المدخلات العشوائية الصغيرة، ومقارنة نتيجة الخوارزمية الخاصة بك على كل منها بنتيجة أسلوب القوة الغاشمة المعروف والصحيح.