0Pricing
Coding Interview Prep · レッスン

ソート済み配列での Two Pointers

両端を内側へ動かして目標値に到達します

「ソート済み配列での Two Pointers」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

なぜ2ポインタ法なのか

2ポインタ法では、入れ子のループの代わりに2つのインデックスで配列を走査します。そのため、多くの O(n^2) の考え方を、すっきりした1回の O(n) の走査に変えられます。🎯

ソート済みが鍵

典型的な方法では、ソート済みの配列が必要です。順序があることで、右へ動けば値が大きくなり、左へ動けば小さくなると判断できるため、各ステップで確実に選択できます。

両端から2ポインタ

一方のポインタを配列の left 端に、もう一方を右端に置きます。2つのポインタは向かい合い、少しずつ間隔を縮めていきます。

left = 0
right = len(a) - 1

両端を内側へ動かす

各ステップでは、ポインタを必ず1つだけ内側へ動かします。配列の順序から、目的に近づくためにどちら側を動かすべきかが分かります。

ループ条件

left < right の間、ループを続けます。2つが一致するか交差したら、調べるべき有効なペアをすべて確認し終えているため、停止できます。

while left < right:
    # inspect a[left] and a[right]
    pass

現在の合計を読む

a[left] + a[right] を現在の候補として確認します。これを目標値と比較すれば、次にもっと大きい値が必要か、もっと小さい値が必要かが分かります。

total = a[left] + a[right]

小さすぎる場合: left を動かす

合計が目標値より小さい場合は、もっと大きい値が必要です。配列は昇順にソートされているため、left ポインタを右へ動かして大きい値に近づけます。

if total < target:
    left += 1

大きすぎる場合: right を動かす

合計が目標値より大きい場合は、もっと小さい値が必要です。right ポインタを左へ動かして小さい値に近づけ、合計を減らします。

elif total > target:
    right -= 1

一歩ごとに不要な処理を捨てる

ポインタを動かすたびに、調べる必要のないペアをまとめて排除できます。そのため、走査の計算量は二次ではなく線形になります。

正しさが保たれる理由

一致する可能性がないペアだけを捨てるため、正しい答えを飛ばすことはありません。この安全性が、競技プログラミングで2ポインタ法を信頼できるものにしています。

両端を超えた応用

同じ考え方は、インプレース反転、分割、マージなどの派生形にも使えます。ポインタが出会う仕組みを理解すれば、これらもすべて身近に感じられます。

確認問題

ソート済み配列を両端から走査して、目標の合計を探しています。

まとめ

2ポインタ法では、ソート済み配列を両端から走査し、left < right の間、各ステップで一方を内側へ動かします。線形時間で正しく動作し、多くのテクニックの基礎になります。🚀

よくある質問

「ソート済み配列での Two Pointers」レッスンは無料ですか？

はい。「ソート済み配列での Two Pointers」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「ソート済み配列での Two Pointers」で何を学びますか？

両端を内側へ動かして目標値に到達します ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

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

「ソート済み配列での Two Pointers」レッスンにはどのくらい時間がかかりますか？

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

このCoding Interview Prepレッスンでコードを書いて実行できますか？

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

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

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