3Sum Pourquoi cette solution O(nlogn) ne fonctionne pas ?

Question

J'ai fait LeetCode et abordé le problème du 3Sum et j'ai d'abord essayé de faire une solution O(nlogn) et après avoir vu la solution proposée, je vois que la solution est $O(n^2)$ ou $O(n^2 imes \log n)$ et pas seulement cela, mais le problème est un sujet très étudié, donc je ne pense pas avoir trouvé une meilleure solution, mais je ne vois pas pourquoi mon approche ne fonctionnerait pas, je peux utiliser de l'aide pour la comprendre.

Le problème est le suivant
Trouver trois nombres dans un tableau tel que $a + b + c = t$,
le Problème LeetCode est légèrement différent dans lequel vous devez trouver la somme la plus proche.

Mon code est le suivant :

1. Triez le tableau.
2.   Commencez avec deux pointeurs i=0 et j= last element of array
3.     Utiliser la recherche binaire entre i et j trouver m tel que arr[m] == target - arr[i] - arr[j], si une telle m n'existe pas retour m tel que arr[m] est le plus proche.
4.     Si arr[i] + arr[m] + arr[j] == target alors tu as fini.
5.     Sinon si arr[i] + arr[m] + arr[j] < target puis ajoutez 1 à i sinon soustraire 1 forme j.
6. Répétez 3 → 5 jusqu'à ce que j - i == 2
7. Retourner le meilleur trouvé i,m,j

La logique de l'étape 5 est que si la solution trouvée est inférieure à l'objectif, nous devrions alors augmenter i de sorte que notre prochaine supposition est plus grande.

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

Cela échoue, par exemple, pour [1, 9, 55, 55, 100], t=111.La première itération trouve 110 et augmente i pour exclure 1 comme possibilité, mais la seule solution, [1, 55, 55], a besoin de 1.

Le problème fondamental est que lorsque vous augmentez i ou réduisez j, vous supposez que l'élément que vous venez de dépasser n'est pas nécessaire - qu'il existe une solution qui ne l'inclut pas.Mais cela n’est justifié par rien, et il se pourrait bien que toutes les solutions aient besoin de cet élément.

Un excellent moyen de tester des idées d'algorithmes comme celle-ci est d'écrire un petit programme qui génère de nombreuses petites entrées aléatoires et de comparer le résultat de votre algorithme sur chacune d'elles au résultat d'une approche par force brute connue et correcte.