一緒に追加された要素のペアが別の整数と等しいかどうかを確認し、それが線形時間で実行されるようにする関数をとる方法？

Question

私はソートされたリストと整数をとり、リスト内の要素のペアの合計が整数に等しいかどうかをチェックする関数をPythonで書く必要があります。また、線形時間（またはO（n）時間）で実行する必要があります。私はタスクを完了する機能を持っていますが、それは二次的な時間で実行されます。ここに私の機能は次のとおりです。

def sum_to_int(l, k): 
    Lst=sorted(l) 
    for i in range(len(Lst)): 
      for n in Lst[i:]: 
        print(Lst[i]+n==k) 

def main(): 
    l=[1, 2, 3, 4, 5, 6] 
    k=10 
    sum_to_int(l, k) 

if __name__=="__main__": 
    main() 

私はこの実行を行うために線形時間で、私は2番目のforループを削除する必要があることはかなり確信しているが、私は、私はせずにリストを通過することができる方法のわからないんだけど2番目のループ。とにかく私はこの機能を簡素化することができます&それは線形時間で実行するには？どんな助けでも大歓迎です。読んでくれてありがとう。

Answer 1

Pythonにあまり堪能ではないので、おそらく私のコードはPythonではありません。誰かが同じようにいくつかのきちんとしたコードを提供できる場合は、自由に編集してください:)。とにかく、基本的な考え方は以下の通りです：
リストから外れた値のペアについては、その合計が検索された値より小さければ小さい方の次の値を試します。その合計が検索された値より大きい場合、ペアのうち大きいほうの次の小さな値を試します。そうでなければ、一致を見つけて、リスト内の次のペアを終了するか試してみることができます。これはO(n)で実行されます。

def find_sum(ls, k): 
    l, u = 0, len(ls) - 1 
    while l < u: 
     sum = ls[l] + ls[u] 
     if sum == k: 
      print("Found: {} + {} = {}".format(ls[l], ls[u], k)) 
      l += 1 
      u -= 1 
     elif sum < k: 
      l += 1 
     else: 
      u -= 1 

例えば：

l = [1, 3, 4, 9, 10, 23, 56], k = 13 

1 3 4 9 10 23 56 
1        56 = 57 => too large, reduce upper value 
1       23  = 24 => too large -=- 
1     10    = 11 => too small, try with larger value 
    3    10    = 13 => found a match, try with the next number-pair 
      4 9     = 13 => found another match 

あなたはそれが動作するという事実に依存しており、あなたが証拠に興味を持っている場合を除き、次のセクションを無視することができます。

この動作の詳細： lsの下位/上位値のインデックスをlとuとします。今すぐlを修正しましょう。すると、u1とu2のように、ls[l] + ls[u1] < kとls[l] + ls[u2] > kのようなインデックスが存在する可能性があります（u1が最大、u2が最小）。 u1とu2で定義されているウィンドウでは、u'とし、u1 < u' < u2とします。 u'が存在する場合は、ls[l] + ls[u'] = kと一致する値を保持する必要があります。それ以外の場合はlが増加し、新しいlについてはu'を検索し続けます。当然、u' <= u1は保持する必要があります。それ以外の場合は、リストの順序制約が破られます。 l >= u1に到達すると、検索スペースを使い果たしたときに新たなペアが現れなくなり、アルゴリズムが終了します。

Answer 2

あなたはセットでかなり簡単にこれを行うことができます。二度番号を使用して問題があるかもしれません

def sum_to_int(sum_value, sorted_ints): 
    s = set(sorted_ints) 
    return any((sum_value - v) in s for v in s) 

、例えば、​​はTrueを返しますが、あなたはcollections

から Counterを使用することによってこの問題を解決することができ