0Pricing
Coding Interview Prep · レッスン

条件を満たすウィンドウを数える

at-most-K から at-most-(K-1) を引くテクニックです

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

測るのではなく数える

最長のものを探すのではなく、条件を満たす部分配列の個数を求めなければならない場合があります。小さな工夫で、これを簡単なスライディングウィンドウの処理に変えられます。🔢

ちょうど K の難しさ

何らかの要素をちょうど K 個含む部分配列を直接数えるのは扱いにくい問題です。境界が頻繁に変わるため、1 つの単純なウィンドウで処理するのが難しくなります。

高々 K への言い換え

要素を高々 K 個含む部分配列なら、1 つのウィンドウで簡単に数えられます。right を拡張すると、条件を満たす left ごとに 1 つの部分配列を数えられます。

引き算のテクニック

ちょうど K は atMost(K) minus atMost(K - 1) で求められます。簡単な 2 つの個数を組み合わせることで、本当に欲しい難しい個数を計算できます。

answer = at_most(k) - at_most(k - 1)

ヘルパーを作る

部分配列に含まれる要素が高々 k 個になるものを数える関数を 1 つ作ります。この関数はウィンドウをスライドさせ、個数が k を超えるたびに縮小します。

def at_most(k):
    left = 0
    total = 0

条件違反時に縮小する

right を拡張してウィンドウを更新します。ウィンドウ内の個数が k より多い間は、left を前に進めて範囲内に戻します。

    while count > k:
        # remove a[left]
        left += 1

ウィンドウの個数を加える

ウィンドウを修正すると、right で終わり、left 以降の位置から始まるすべての部分配列が有効になります。right - left + 1 を加えてください。

    total += right - left + 1

この個数で数えられる理由

right を固定すると、有効な開始位置は left、left+1、そして right までです。これはちょうど right - left + 1 個の部分配列で、すべてが「高々 k 個」の条件を満たします。

2 回の呼び出しを組み合わせる

ヘルパーを 2 回実行して減算します。各呼び出しは O(n) なので、ちょうど K の個数を求める全体の計算量も線形のままです。

return at_most(k) - at_most(k - 1)

端のケースを処理する

k が 0 のとき、atMost(k - 1) では -1 を使うことになります。ヘルパーが意味のある 0 個を返せるよう、このケースを処理してください。

適用できる場面

この高々の個数同士を引く方法は、異なる値がちょうど K 個ある部分配列、奇数が K 個ある部分配列、その他のウィンドウごとに単調な性質を持つ問題の個数計算に使えます。

確認

異なる要素をちょうど K 個含む部分配列の個数を求めます。

まとめ

ちょうど K の個数は、単に atMost(K) minus atMost(K - 1) です。各ヘルパーは O(n) でウィンドウをスライドさせるため、全体の個数計算も線形時間で実行できます。✅

よくある質問

「条件を満たすウィンドウを数える」レッスンは無料ですか？

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

「条件を満たすウィンドウを数える」で何を学びますか？

at-most-K から at-most-(K-1) を引くテクニックです ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

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

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

「条件を満たすウィンドウを数える」レッスンにはどのくらい時間がかかりますか？

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

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

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

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

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