Python：実行時間を改善する：total_untimesが正確な飛行長と等しい2つのmovie_lengthを選択する

Question

私は別のインタビューの質問をしています。

私は、合計ランタイムが正確な飛行時間に等しい2つの映画を選択するための機能を構築しています。 整数のflight_length（分）と整数のリストmovie_lengths（分）を引数にとり、movie_lengthの2つの数値の和がflight_lengthに等しいかどうかを示すブール値を返します。

まず最初に、2つのループ（外側はfirst_movie_lengthを選択し、内側はsecond_movie_lengthを選択）を実行すると考えました。それは私たちにO（n^2）の実行時間を与えますO（n2）

しかし、私たちはもっとうまくいく可能性はありますか？

def can_two_movies_fill_flight(movie_lengths, flight_length): 

# movie lengths we've seen so far 
movie_lengths_seen = set() 

for first_movie_length in movie_lengths: 

    matching_second_movie_length = flight_length - first_movie_length 
    if matching_second_movie_length in movie_lengths_seen: 
     return True 

    movie_lengths_seen.add(first_movie_length) 

# we never found a match, so return False 
return False 

私は、このソリューションは私にO（n）の時間を与えると思うし、O（n）はO（n）のスペース：

は、私は、次の解決策を持っています。

ハッシュマップを使用することは可能でしょうか？

Answer 1

最初にmovie_lengthsをソートすると、O（n）O（n）時間の代わりにO（\ lg {n}）O（lgn）時間でsecond_movie_lengthを見つけるためにバイナリ検索を使用できます。 しかしソートはO（nlg（n））O（nlg（n））の費用がかかります。

私の解決策： 私たちのデータ構造としてセットを使用する。 movie_lengthsを1回通過させ、各項目をfirst_movie_lengthとして扱います。各反復で。

flight_length - first_movie_lengthに等しい（movie_lengths_seenセットに格納されている）match_second_movie_lengthが既に存在するかどうかを確認してください。もしあれば、我々は短絡して真を返す。 現在のfirst_movie_lengthを投げて、movie_lengths_seenを最新の状態に設定してください。

def can_two_movies_fill_flight(movie_lengths, flight_length): 

    # movie lengths we've seen so far 
    movie_lengths_seen = set() 

    for first_movie_length in movie_lengths: 

     matching_second_movie_length = flight_length - first_movie_length 
     if matching_second_movie_length in movie_lengths_seen: 
      return True 

     movie_lengths_seen.add(first_movie_length) 

    return False 

我々は、ユーザーが、我々はそれにfirst_movie_lengthを入れている前に、私たちはmatching_second_movie_lengthためmovie_lengths_seenをチェックするため、tは二回同じ映画を見'を獲得した知っています！

効率とアルゴリズムの複雑さ：O（n）O（n）時間、O（n）O（n）時間。ランタイムを最適化するには、少しのスペースコストを追加しました。