3Summe Warum funktioniert diese O(nlogn)-Lösung nicht?

Question

Ich habe LeetCode gemacht und mich mit dem Problem der 3Summe befasst. Zuerst habe ich versucht, eine O(nlogn)-Lösung zu erstellen, und nachdem ich die vorgeschlagene Lösung gesehen habe, sehe ich, dass die Lösung vorhanden ist $O(n^2)$ oder $O(n^2 imes \log n)$ Und nicht nur das, das Problem ist ein sehr gut erforschtes Thema, daher glaube ich nicht, dass ich eine bessere Lösung gefunden habe, kann aber nicht verstehen, warum mein Ansatz nicht funktionieren würde, ich kann Hilfe gebrauchen, um es herauszufinden.

Das Problem ist folgendes
Finden Sie drei Zahlen in einem solchen Array $a + b + c = t$,
Die LeetCode-Problem ist etwas anders, bei dem Sie die nächstliegende Summe finden müssen.

Mein Code ist der folgende:

1. Sortieren Sie das Array.
2.   Beginnen Sie mit zwei Hinweisen i=0 Und j= last element of array
3.     Verwenden Sie die binäre Suche zwischen i Und j finden m so dass arr[m] == target - arr[i] - arr[j], wenn ja m existiert nicht zurück m so dass arr[m] ist am nächsten.
4.     Wenn arr[i] + arr[m] + arr[j] == target dann bist du fertig.
5.     Ansonsten wenn arr[i] + arr[m] + arr[j] < target dann 1 hinzufügen i sonst subtrahiere 1 Form j.
6. Wiederholen Sie 3 → 5 bis j - i == 2
7. Geben Sie das Beste zurück, was Sie gefunden haben i,m,j

Die Logik in Schritt 5 besteht darin, dass wir erhöhen sollten, wenn die gefundene Lösung unter dem Ziel liegt i so dass unsere nächste Vermutung größer ist.

Code:

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

Dies schlägt beispielsweise für [1, 9, 55, 55, 100], t=111, fehl.Die erste Iteration findet 110 und erhöht i, um 1 als Möglichkeit auszuschließen, aber die einzige Lösung, [1, 55, 55], benötigt 1.

Das Grundproblem besteht darin, dass Sie, wenn Sie i erhöhen oder j verringern, davon ausgehen, dass das Element, über das Sie gerade hinausgegangen sind, nicht benötigt wird – dass es eine Lösung gibt, die es nicht enthält.Dies ist jedoch durch nichts zu rechtfertigen, und es könnte durchaus sein, dass alle Lösungen dieses Element benötigen.

Eine gute Möglichkeit, solche Algorithmusideen zu testen, besteht darin, ein kleines Programm zu schreiben, das viele kleine Zufallseingaben generiert, und das Ergebnis Ihres Algorithmus für jede davon mit dem Ergebnis eines bekanntermaßen korrekten Brute-Force-Ansatzes zu vergleichen.