3Sum Perché questa soluzione O(nlogn) non funziona?

Question

Ho eseguito LeetCode e ho affrontato il problema del 3Sum e prima ho provato a fare una soluzione O(nlogn) e dopo aver visto la soluzione proposta vedo che la soluzione è $O(n^2)$ O $O(n^2 imes \log n)$ e non solo, ma il problema è un argomento altamente studiato, quindi non penso di aver trovato una soluzione migliore ma non riesco a capire perché il mio approccio non funzionerebbe, posso usare aiuto per capirlo.

Il problema è il seguente
Trova tre numeri in un array come questo $a + b + c = t$,
IL Problema LeetCode è leggermente diverso in cui devi trovare la somma più vicina.

Il mio codice è il seguente:

1. Ordina la matrice.
2.   Inizia con due puntatori i=0 E j= last element of array
3.     Utilizza la ricerca binaria tra i E j trovare m tale che arr[m] == target - arr[i] - arr[j], se tale m non esiste il ritorno m tale che arr[m] è il più vicino.
4.     Se arr[i] + arr[m] + arr[j] == target allora hai finito.
5.     Altrimenti se arr[i] + arr[m] + arr[j] < target quindi aggiungi 1 a i altrimenti sottrai 1 forma j.
6. Ripetere 3 → 5 fino a j - i == 2
7. Restituisci il meglio trovato i,m,j

La logica del passaggio 5 è che se la soluzione trovata è inferiore all’obiettivo allora dovremmo aumentare i in modo tale che la nostra prossima ipotesi sia più grande.

Codice:

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

Ciò fallisce, ad esempio, per [1, 9, 55, 55, 100], t=111.La prima iterazione trova 110 e aumenta i per escludere 1 come possibilità, ma l'unica soluzione, [1, 55, 55], necessita di 1.

Il problema di base è che quando aumenti i o riduci j, stai presupponendo che l'elemento che hai appena superato non sia necessario: che esista una soluzione che non lo include.Ma questo non è giustificato da nulla, e potrebbe benissimo essere che tutte le soluzioni necessitino di quell’elemento.

Un ottimo modo per testare idee di algoritmi come questo è scrivere un piccolo programma che generi molti piccoli input casuali e confrontare il risultato dell'algoritmo su ciascuno di essi con il risultato di un approccio di forza bruta noto e corretto.