0Pricing
Competitive Programming Academy · レッスン

Two Pointers による可変ウィンドウ

条件を満たすまで拡大・縮小します

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

ウィンドウの長さが変わる場合

ウィンドウの長さを固定しない問題もあります。その場合は、合計を上限以下に保つといった条件を満たすように、ウィンドウを拡大したり縮小したりします。

2 つのポインターで 1 つのウィンドウを扱う

left と right という 2 つのインデックスで、ウィンドウの両端を管理します。right ポインターが拡張し、必要なときに left ポインターが後ろから追いついて縮小します。

left = 0
window = 0

右に拡張する

right を使ってすべての要素を右方向に走査し、各要素をウィンドウに含めます。新しい値を合計に加えるなど、逐次的に管理している状態を更新します。

for right in range(n):
    window += a[right]

必要なときに縮小する

ウィンドウが条件に違反している間は、left を右に移動してその要素を取り除きます。これにより、後戻りせずに条件を満たせる状態へ戻します。

    while window > limit:
        window -= a[left]
        left += 1

有効なウィンドウを読み取る

内側のループが終わると、left から right までのウィンドウは有効です。その長さは right - left + 1 であり、そのまま利用できます。

    length = right - left + 1

最良の結果を記録する

この有効なウィンドウを使って答えを更新します。多くの場合は、これまでに見つかった最長のウィンドウを記録します。見落としがないよう、毎回の反復で行ってください。

    best = max(best, right - left + 1)

線形時間になる理由

各ポインターは前方にしか進まず、後戻りしません。left と right を合わせても最大 n ステップしか進まないため、全体の走査は O(n) です。

単調性が必要

これは、ウィンドウを拡張すると条件を満たすことが難しくなる場合に使えます。この単調な性質があるため、left を後戻りさせずに済みます。

最長と最短の違い

最短の有効なウィンドウを求める場合は、条件をまだ満たしている間は縮小し、条件を破る前に記録します。ポインターの仕組みは同じです。

    while window >= target:
        best = min(best, right - left + 1)
        window -= a[left]
        left += 1

空のウィンドウに注意する

縮小によってウィンドウが空になる可能性がある場合は、left が right を追い越すことを防いでください。また、答えが実際に見つかったことを確認してから返してください。

パターンを見抜く

要素に関する条件を満たす連続した区間のうち、最長または最短のものを求める問題では、可変長ウィンドウを使えないか考えてみてください。

確認

サイズ n の配列に対して、2 ポインターの可変長ウィンドウを動かします。

まとめ

right を伸ばして要素を含め、条件に違反している間は left を縮め、有効な各ウィンドウを記録します。前方にしか進まないポインターにより、計算量は O(n) です。✅

よくある質問

「Two Pointers による可変ウィンドウ」レッスンは無料ですか？

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

「Two Pointers による可変ウィンドウ」で何を学びますか？

条件を満たすまで拡大・縮小します ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

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

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

「Two Pointers による可変ウィンドウ」レッスンにはどのくらい時間がかかりますか？

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

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

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

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

  1. 固定サイズウィンドウの合計
  2. Two Pointers による可変ウィンドウ
  3. 重複のない最長部分文字列
  4. 条件を満たすウィンドウを数える
← Competitive Programming Academyに戻る