2つの要素の合計が特定の数に等しい2つのソートされた配列

Question

私はいくつかの助けを得ることができるかと思いました。私は2つのソートされた配列の2つの数字が特定の数に加わるかどうかを判断するためのTHETA（n）または線形時間であるアルゴリズムを探したい。

例えば、我々は2つのソート配列としましょう：私はXの要素と正確に一定数まで追加Yの要素があるかどうかを決定したいXとY

を、のは、50を言ってみましょう。

これまでのところ、私はこれらのアルゴリズムをPythonで考え出すことができましたが、THETA（n）ではなくTHETA（n^2）の順序であると確信しています。

def arrayTestOne(X,Y): 
    S =[1 for x in X for y in Y if x+y == 50] 

def arrayTestTwo(X,Y): 
    for x in X: 
     for y in Y: 
      if x + y == 50: 
       print("1") 

私はそれが線形時間を壊すループの2倍だと思っていますが、それ以外の2つのリストを反復する方法はありますか？いかなる考えも認められるだろう。ここで

Answer 1

あなたは何ができるか1つのリスト内で最高で開始し、他の中で最も低い、とチェックサムです。

合計が目標の場合は完了です。

高すぎる場合は、最初のリストの次の値に移動します。

低すぎる場合は、2番目に低い値に移動します。

ターゲットに到達せずに両方のリストを通過すると、falseが返されます。

Answer 2

てもソートは必要ありません。あなたのための2Nである：

def check_array(x, y, needed_sum): 
    y = set(y) 
    return next(((i, needed_sum-i) for i in x if (needed_sum-i) in y), None)