目標の合計を持つ部分配列を数える
累積和とハッシュマップを組み合わせます
「目標の合計を持つ部分配列を数える」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。
もう一段難しい問題
ここで応用です。合計が目標値 k になる部分配列がいくつあるかを数えます。すべての組み合わせを調べる方法は遅いですが、累積和とハッシュマップを組み合わせれば解決できます。🎯
累積和で捉え直す
部分配列の合計は prefix[r + 1] から prefix[l] を引いた値です。つまり合計が k になるには、2 つの prefix の値の差がちょうどkになればよいのです。
重要な式変形
現在の prefix が P なら、P - k と等しい、それより前の prefix が必要です。この式変形が、解法の核心です。
need = current_prefix - k検索せずに数える
その都度後ろに向かって調べる代わりに、各 prefix の値がこれまでに何回現れたかを記録します。この出現回数を更新すれば、O(1) で答えられます。
出現回数マップを使う
辞書を使って、各 prefix の値を、その値が現れた回数に対応付けます。このマップによって、検索を即座のカウントに変えられます。
from collections import defaultdict
seen = defaultdict(int)空の prefix を初期登録する
ループの前に、prefix 0 が 1 回現れたことを記録します。この初期値により、インデックス 0 から始まる部分配列も数えられます。
seen[0] = 11 回のループで処理する
各要素について、累積中の prefix を更新し、必要な値の出現回数を答えに加えてから、現在の prefix を記録します。これだけで1 回の走査が完了します。
total += x
count += seen[total - k]
seen[total] += 1順序が重要な理由
現在の prefix を記録する前に、答えへ加算しなければなりません。そうしないと長さ 0 の区間が紛れ込み、カウントが壊れてしまいます。
速度面での利点
各要素に対して定数時間の処理を行うため、全体のカウントはO(n)で完了します。大きな入力では、O(n^2) の全探索より高速です。
負の数にも対応
スライディングウィンドウとは異なり、この方法は負の数にも問題なく対応できます。符号に関係なく、prefix の差が有効だからです。
典型的な利用例
このパターンは、有名な「部分配列の合計が k」問題や、競技プログラミングの問題に現れるさまざまな派生問題を解決します。
確認問題
累積中の prefix は P、目標値は k です。
まとめ
累積和と出現回数マップを使えば、合計が目標値になる部分配列をO(n)で数えられます。prefix 0 を初期登録し、現在の prefix を記録する前にカウントしてください。✅
よくある質問
「目標の合計を持つ部分配列を数える」レッスンは無料ですか？
はい。「目標の合計を持つ部分配列を数える」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。
「目標の合計を持つ部分配列を数える」で何を学びますか？
累積和とハッシュマップを組み合わせます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Competitive Programming Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「目標の合計を持つ部分配列を数える」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCompetitive Programming Academyレッスンでコードを書いて実行できますか？
はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 累積和配列を構築する
- 引き算で任意の範囲を合計する
- 目標の合計を持つ部分配列を数える
- 区間更新のための差分配列