4

以下は、「Amazon」が私に尋ねたインタビューの質問です。私はまだ最適化されたソリューションを考え出していません。

問題文:
ソートされていない整数 n の配列が与えられます。その配列からの整数の追加がターゲット値と一致する場合は「true」を返し、そうでない場合はfalse を返します。

ノート： 

   1)'n' could be 1000 or 10,000.
   2) Target value could be 'negative'
   3) It may be addition of any 'k' integers (not only two) , where k<=n.

テスト条件:

    i/p:- Array A[]= {6,7,3,0,12,-5,-6,100}
    Target =  8
    o/p:- TRUE        
As, 6+7+(-5)=8

線形または通常に実行しようとすると、O(2^n) 時間の複雑さがかかります。
したがって、この問題をさらに最適化する方法またはアルゴリズムを探しています。

前もって感謝します！

4

3 に答える 3

9

部分和問題はよく知られた NP 完全問題です。ここでは、ターゲットに合計する数値のセットを探していると仮定します (実際に 2 つの数値のみを探している場合は、O(n で実行されるカウント ハッシュテーブルを使用した 5 行のソリューションがあります) ） 時間）。

2 つの基本的なアプローチがあります。1 つ目は、考えられるすべてのサブシーケンスをテストすることです。すでに観察したように、これには O(2 n ) 時間 (指数関数的) がかかり、n が 1000 の場合は扱いにくいです。

2 つ目は、リストのプレフィックスから取得できる合計を追跡することです。これは非常に単純なアプローチであり、整数が制限されている場合にうまく機能します。例として、入力が n k ビットの整数である場合、計算量は O(2 k n 2 ) (疑似多項式) になります。合計が取得できる最大値は 2 k n であるため、テーブルには最大で 2 k nが含まれます。 2エントリ。これは典型的な動的計画法のアプローチであり、部分問題はT[s][k] = (A[1..k] has a subsequence summing to s)であり、最終的な解は で与えられT[target][n]ます。

これを実装する Python のソリューションを次に示します。

def subset_sum(A, target):
    T = {0} # T[s][0] = (TRUE iff s == 0)
    for i in A:
        T |= {x + i for x in T}
    return target in T

例:

>>> subset_sum([-5,6,7,1,0,12,5,-6,100], 13)
True
>>> subset_sum([95, -120, 22, 14491], 13)
False

おまけ: 興味がある方は、ペアサム問題の解決策をご覧ください。これは O(n) 時間で実行され、配列にターゲットに合計される 2 つの数値があるかどうかがわかります。

from collections import Counter
def pair_sum(A, t):
    C = Counter(A)
    for k,v in C.iteritems():
        if t == k+k and v > 1: return True # k is in the array twice
        elif t != k+k and t-k in C: return True
    return False

例:

>>> pair_sum([3,3,3,4], 13)
False
>>> pair_sum([3,3,3,10], 13)
True
>>> pair_sum([7,7,2], 14)
True
>>> pair_sum([7,14,2], 14)
False
于 2013-02-01T18:26:43.300 に答える
1

注この回答はまだ有益であるため、そのままにしておきますが、OPの編集後は関連性が低くなります。

「ハッシュ」と呼ばれる概念を使用して、O(n)ランタイムの複雑さとスペースの複雑さを解決する方法を次に示します。O(n)(n は配列のサイズ)

かけたい番号にかけようd

まず、ある種のHashTable(キー値ストア) を作成します。HashMap にはO(1)、insert、get、contains があります。ここでそれらについて読むことができます

次に、ハッシュ マップのセル d オブジェクトにすべてのオブジェクトを配置します。次の数値 x を確認する前に、ハッシュ マップにセル x の値が含まれているかどうかを確認します。一致する場合は、一致が見つかりました。

ここにいくつかの疑似コードがあります（これはCコードよりも一般的な答えの方が良いと思います）

CheckIfTwoNumbersComplementTo(d,arr)
    map <-- new HashTable
    for each number x in Arr
        if(map contains a key for x)
            return true
        else
            add d-x to map if it is not already in map
    return false
于 2013-02-01T03:46:22.347 に答える
0

配列をソートし、各要素について、ターゲット値に必要なペアを計算して検索するのはどうですか? これにより、ソートのコスト + 各二分探索のコストが加算されます。

于 2013-02-01T03:52:09.547 に答える