リスト内の整数ペア(2つの整数要素)の合計がターゲット値なればTrueを返す

Why was my algorithm for this interview a sub-optimal approach? – StackOverflow

何を以って最適化とするのか分からないけど.
空間効率の観点で云えば,「itertools.combinations」を使えば良い.
イテレータを返すので,メモリ中に中間結果を作らずメモリ効率が良い.

import sys
a = itertools.combinations(range(1, 10), 2)
b = itertools.combinations(range(1, 100), 2)

print(sys.getsizeof(a))
print(sys.getsizeof(list(a)))
print(sys.getsizeof(b))
print(sys.getsizeof(list(b)))

88
384
88
40824

以下の処理は,時間効率はO(n**2)だが,空間効率はO(1).
(最初のリストを含めれば,全体の空間効率は勿論O(n))

import itertools

lst = [1,5,3,2,6]
tval = 6
for x in itertools.combinations(lst, 2):
  if sum(x) == tval:
    print('True')
    break

True

時間効率はO(n2)といっても,全ての組み合わせを調べる訳じゃないし,
とにかく「ターゲットを満たす2和が存在するか」だけの話なので,
最悪時間効率がO(n
2)なだけで,処理前にソートするとか,
ちょっと工夫すればこれで十分だと思う.

ちなみに,(効率は悪いけど)ワンライナーならこう.

any(sum(x) == tval for x in itertools.combinations(lst, 2))

True
 
 

関連:
部分集合和問題

Maximum subarray problem

部分和問題

配列要素の合計値がターゲット値になる様な組み合わせを全て求める

How can I list all of the ways to sum a list of numbers to N, with repeats, in python?

素数の和で数値を表現

広告
カテゴリー: 未分類 パーマリンク

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください