3Sum Почему это решение O(nlogn) не работает?

Question

Я занимался LeetCode и решил проблему 3Sum, и сначала я попытался сделать решение O (nlogn), и, увидев предложенное решение, я увидел, что решение $O(n^2)$ или $O(n^2 imes \log n)$ и не только это, но проблема является тщательно исследованной темой, поэтому я не думаю, что нашел лучшее решение, но не понимаю, почему мой подход не сработает, могу использовать помощь, чтобы разобраться в этом.

Проблема в следующем
Найдите три числа в массиве такие, что $а + б + с = т$,
тот Проблема с LeetCode немного отличается, в котором вам нужно найти ближайшую сумму.

Мой код следующий:

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, вы предполагаете, что элемент, мимо которого вы только что прошли, не нужен - что существует какое-то решение, которое его не включает.Но это ничем не оправдано, и вполне возможно, что этот элемент нужен всем решениям.

Отличный способ протестировать подобные идеи алгоритмов — написать небольшую программу, которая генерирует множество небольших случайных входных данных и сравнивать результат вашего алгоритма на каждом из них с результатом заведомо правильного метода грубой силы.