3Sum 为什么这个 O(nlogn) 解决方案不起作用？

Question

我一直在做 LeetCode 并解决了 3Sum 的问题，首先我尝试做一个 O(nlogn) 解决方案，在看到建议的解决方案后，我发现解决方案是 $O(n^2)$ 或者 $O(n^2 imes \log n)$ 不仅如此，这个问题是一个经过深入研究的主题，所以我认为我没有找到更好的解决方案，但不明白为什么我的方法不起作用，可以使用帮助来解决它。

问题如下
在数组中找到三个数字，使得 $a + b + c = t$,
这 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 时，您假设不需要您刚刚前进的元素 - 存在一些不包含它的解决方案。但这没有任何理由可以证明，而且很可能所有解决方案都需要该元素。

测试这样的算法想法的一个好方法是编写一个小程序，生成许多小的随机输入，并将每个输入的算法结果与已知正确的暴力方法的结果进行比较。