sumOfTwo時間制限超過CodeFightsインタビュー実践

Question

私はCodeFights.comでsumOFTwoチャレンジを試みていますが、私は解決策を見るために残念ながらそれを完了できません。すべての私のテストは15回目の隠れテストまで続き、それは時間制限を超えていると言います。

課題は次のとおりです：aとbと整数の目標値vの2つの整数配列があります。数字のペアがあるかどうかを判定します。 vの合計を得るために一緒に加算されます。そのようなペアが存在する場合はtrueを返し、そうでない場合はfalseを返します。

私のコードがある -

def sumOfTwo(a,b,v): 
    a.sort() 
    b.sort() 

    if(0 in a and v in b): 
     return True 
    elif(v in a and 0 in b): 
     return True 
    else: 
     for i in a: 
      for j in b: 
       if(i + j == v): 
        return True 
    return False 

私はそれがコードの約6行まで収縮することができますが、私は速く終える可能性のコードを助けることができるの行に追加する保持知っています。その他の最適化がありませんか？

Answer 1

あなただけの他のリストを反復処理し、v - value_from_listが中に存在するかどうかを確認し、setにリストの1を回すことができるset：

def sumOfTwo(a,b,v): 
    b = set(b) 

    return any(v - x in b for x in a) 

print(sumOfTwo([3, 6, 7], [2, 1], 9)) 
print(sumOfTwo([3, 6, 7], [2, 1], 10)) 
print(sumOfTwo([3, 6, 7], [2, 1], 4)) 
print(sumOfTwo([3, 6, 7], [2, 1], 3)) 

出力：上記の

True 
False 
True 
False 

時間の複雑さO（n）。

Answer 2

これは私が持っているものです。それは隠されたすべてのテストに合格しますが、隠されたテストのうちの4つには時間がかかります。

def sumOfTwo(a, b, v): 
    for i in a: 
    if((v-i) in b): 
     return True 
    return False 

@ niemmiの回答は期限部分を過ぎます。私はセットが配列/リストより速いことを知らなかった。ありがとう、よく知っています。 forループの前にb=set(b)を追加すると、ループが終了します。