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を見つけ、可能性として1を除外するために増加しますが、唯一の解決策[1,55,55]、1。

基本的な問題は、あなたがIを増やすかjを減らすとき、あなたはあなたが過去だけ上に進んでいる要素が必要ではないと仮定しています - それを含まない解決策がいくつか存在することを想定しています。しかし、これは何にも正当化されていません、そしてそれはすべての解決策がその要素を必要とすることがよくあり得る。

アルゴリズムのアイデアをテストするのに最適な方法は、多くの小さなランダム入力を生成する小さなプログラムを作成し、それぞれのアルゴリズムの結果を既知の訂正されたブルートフォースアプローチの結果と比較することです。