3Sum ¿Por qué esta solución O(nlogn) no funciona?

Question

He estado haciendo LeetCode y abordé el problema de 3Sum y primero intenté hacer una solución O(nlogn) y después de ver la solución propuesta veo que la solución es $O(n^2)$ o $O(n^2 \veces \log n)$ y no solo eso, sino que el problema es un tema muy investigado, por lo que no creo haber encontrado una solución mejor, pero no veo por qué mi enfoque no funcionaría, puedo necesitar ayuda para resolverlo.

El problema es el siguiente
Encuentre tres números en una matriz tal que $a + b + c = t$,
el Problema de código Leet es ligeramente diferente en el que necesitas encontrar la suma más cercana.

Mi código es el siguiente:

1. Ordena la matriz.
2.   Comience con dos consejos i=0 y j= last element of array
3.     Utilice la búsqueda binaria entre i y j encontrar m tal que arr[m] == target - arr[i] - arr[j], si tal m no existe volver m tal que arr[m] es el más cercano.
4.     Si arr[i] + arr[m] + arr[j] == target entonces has terminado.
5.     De lo contrario si arr[i] + arr[m] + arr[j] < target luego suma 1 a i de lo contrario resta 1 formulario j.
6. Repita 3 → 5 hasta j - i == 2
7. Devolver lo mejor encontrado i,m,j

La lógica en el paso 5 es que si la solución encontrada es menor que el objetivo entonces debemos aumentar i de modo que nuestra próxima suposición es mayor.

Código:

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

Esto falla, por ejemplo, [1, 9, 55, 55, 100], t=111.La primera iteración encuentra 110 y aumenta i para excluir 1 como posibilidad, pero la única solución, [1, 55, 55], necesita 1.

El problema básico es que cuando aumentas i o reduces j, estás asumiendo que el elemento que acabas de avanzar no es necesario, que existe alguna solución que no lo incluye.Pero esto no se justifica por nada, y bien podría ser que todas las soluciones necesiten ese elemento.

Una excelente manera de probar ideas de algoritmos como esta es escribir un pequeño programa que genere muchas entradas aleatorias pequeñas y comparar el resultado de su algoritmo en cada una de ellas con el resultado de un enfoque de fuerza bruta correcto y conocido.