0Pricing
Competitive Programming Academy · レッスン

指定された合計になるペアを見つける

O(n^2) の全探索を上回ります

「指定された合計になるペアを見つける」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。

ペア和問題

配列と目標値が与えられたとき、その値になるように足し合わされる2つの値を探します。競技プログラミングで最もよく出る入門問題の1つです。🔍

全探索

分かりやすい方法は、2重ループですべてのペアを試すことです。動作はしますが、全ペアの確認には O(n^2) かかるため、非常に遅くなることがあります。

for i in range(n):
    for j in range(i + 1, n):
        if a[i] + a[j] == target:
            return (i, j)

全探索が破綻する場面

n が 100000 近くになると、O(n^2) は100億回の確認になります。そのため TLE になってしまいます。制約は、もっと速い方法を探すように示しています。

ソートしてから走査

先に配列をソートすれば、両端から2ポインタで1回の走査中に解けます。ソートに O(n log n)、その後の走査に O(n) かかります。

a.sort()
left, right = 0, len(a) - 1

目標値と比較する

各ステップで a[left] + a[right] を確認します。その1つの値だけで、次にどちらへ動くべきかを迷わず決められます。

total = a[left] + a[right]

完全一致: 完了

合計が目標値と等しければ、ペアが見つかったことになります。有効な答えを1つ見つければよいので、すぐに返してください。

if total == target:
    return (left, right)

それ以外は調整する

合計が小さすぎる場合は left を右へ、大きすぎる場合は right を左へ動かします。ソート済みの順序により、どの移動も必ず解に近づきます。

elif total < target:
    left += 1
else:
    right -= 1

ペアが存在しない場合

一致しないままポインタが交差した場合、有効なペアは存在しません。ループが終了したこと自体が、完全な答えになります。

ハッシュセットという選択肢

元のインデックスを保持する必要がある場合は、ハッシュセットのほうが簡潔です。各値について、target からその値を引いた値がすでに出現しているかを確認します。

seen = set()
for x in a:
    if target - x in seen:
        # found
        pass
    seen.add(x)

方法を選ぶ

配列がソート済み、またはソートしてよい場合は2ポインタ法を使います。ソートせずに O(n) を実現したい場合やインデックスを保持する必要がある場合は、ハッシュセットを使います。

重複に注意する

ある値を自分自身と組み合わせられる場合でも、2つのインデックスが異なることを確認してください。left != right または i != j を簡単に確認すれば、この落とし穴を避けられます。

確認問題

目標値になるペアを探すとき、O(n^2) の全探索より速い方法を使いたいとします。

まとめ

2ポインタ法でソートしてから走査すれば、O(n log n) で目標のペアを見つけられます。インデックスが重要な場合はハッシュセットで O(n) にできます。制約に応じて選びましょう。✅

よくある質問

「指定された合計になるペアを見つける」レッスンは無料ですか？

はい。「指定された合計になるペアを見つける」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。

「指定された合計になるペアを見つける」で何を学びますか？

O(n^2) の全探索を上回ります ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。

「指定された合計になるペアを見つける」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. ソート済み配列での Two Pointers
  2. 指定された合計になるペアを見つける
  3. 重複をその場で削除する
  4. 2 つのソート済みシーケンスをマージする
← Competitive Programming Academyに戻る