Guppi StudioPROBLEM 06
合計が目標になる連続区間
合計が target になる連続部分配列の個数を数えます。
日ごとの増減値が配列で与えられます。
連続する1日以上の区間のうち、合計が target と等しくなる区間はいくつあるでしょうか。
subarraySum(nums, target) は区間の個数を返してください。
同じ位置を含む区間同士が重なっていても、それぞれ数えます。
例
入力: nums = [1, 2, 1, 2], target = 3
出力: 3
理由: [1,2]（位置0-1）、[2,1]（位置1-2）、[1,2]（位置2-3）の3区間。位置が違えば別の区間として数える入力: nums = [0, 0, 0], target = 0
出力: 6
理由: 長さ1が3区間、長さ2が2区間、長さ3が1区間で合計6。値が同じでも位置が違えば別の区間制約
1 <= nums.length <= 100,000- 各要素と
targetは安全な整数 - 配列には負数と0を含む
- 目標: O(n) 相当（全区間を試す解法は性能テストで時間切れになります）
対応する問題: LeetCode #560 Subarray Sum Equals K
まず素朴に解くと — 全区間の和を試す
開始位置と終了位置の組み合わせを全部試します。
function subarraySum(nums: number[], target: number): number {
let count = 0;
for (let start = 0; start < nums.length; start += 1) {
let sum = 0;
for (let end = start; end < nums.length; end += 1) {
sum += nums[end];
if (sum === target) count += 1;
}
}
return count;
}区間の数は約 n²/2 なので O(n²) です。内側で和を持ち回っているぶん、3重ループよりはましですが、それでも二乗です。
どこが遅いのか
性能テストは 100,000 要素。区間の総数はおよそ 50億 になり、制限時間に到底収まりません。
ここで「区間が n² 個あるのに、どうやって全部数えるのか？」と感じるはずです。
そのとおりで、すべての区間を1つずつ見ることは諦めます。代わりに、条件を満たす区間をまとめて数える方法を考えます。
発想の転換 1 — 区間和を引き算にする
先頭からの累積和を prefix[i]（先頭から i 番目までの合計）とすると、区間 (i, j] の和は引き算で表せます。
区間 (i, j] の和 = prefix[j] - prefix[i]つまり「和が target の区間」は「差が target になる2つの累積和の組」と同じです。この言い換えで、問題が two-sum とそっくりの形になりました。
発想の転換 2 — 相方を数える
今 j 番目まで見て累積和が prefix だとすると、必要な相方は prefix - target です。それが過去に何回現れたかが、そのまま「j で終わる条件を満たす区間の個数」になります。
two-sum では「相方を1つ見つけたら終わり」でしたが、今回は個数を数えるので、Map の値を位置ではなく出現回数にします。
解答例 — O(n)
function subarraySum(nums: number[], target: number): number {
const frequencies = new Map<number, number>([[0, 1]]);
let prefix = 0;
let count = 0;
for (const value of nums) {
prefix += value;
count += frequencies.get(prefix - target) ?? 0;
frequencies.set(prefix, (frequencies.get(prefix) ?? 0) + 1);
}
return count;
}2つの要点があります。
Map([[0, 1]])から始める — 「まだ何も足していない状態の累積和 0」を1回ぶん登録しておく。これがないと、先頭から始まる区間（prefixそのものが target になる場合）を数え落とします。最も多いバグです。- 数えてから登録する — 先に登録すると、長さ0の空区間を自分自身と組にして数えてしまいます（
target = 0のとき特に致命的）。
動きを追う — nums = [1, 2, 1, 2], target = 3
初期状態: prefix = 0, count = 0, freq = {0→1}
| value | prefix | 探す値 (prefix−3) | 見つかった回数 | count | 更新後の freq |
|---|---|---|---|---|---|
| 1 | 1 | -2 | 0 | 0 | {0→1, 1→1} |
| 2 | 3 | 0 | 1 | 1 | {0→1, 1→1, 3→1} |
| 1 | 4 | 1 | 1 | 2 | {0→1, 1→1, 3→1, 4→1} |
| 2 | 6 | 3 | 1 | 3 | {0→1, 1→1, 3→1, 4→1, 6→1} |
答えは 3。2行目で見つかった 0 は「初期状態」との組、つまり先頭から始まる区間 [1,2] に対応します。ここで初期値 {0→1} が効いています。
なぜ Sliding Window ではないのか
「連続する区間」と聞くと sliding window を使いたくなりますが、この問題では使えません。窓を伸ばすと和が増える、という単調性が必要なところ、nums に負数が含まれるため和は増えたり減ったりするからです。
もし「全要素が正」という制約なら sliding window で O(1) 領域まで落とせます。面接で「負数がある場合は？」と聞かれるのはこの違いを見ているので、制約に負数があるかを最初に確認するのが定石です。
計算量の比較
| 解法 | 時間 | 追加領域 | n = 100,000 での目安 |
|---|---|---|---|
| 全区間を試す | O(n²) | O(1) | 約50億 |
| 累積和 + 頻度 Map | O(n) | O(n) | 約10万 |
面接でどう話すか
「全区間を試すと O(n²) です。区間和は累積和の差なので、『差が target になる累積和の組を数える』問題に言い換えられます。各位置で
prefix - targetの過去の出現回数を足していけば O(n) です。累積和0を1回ぶん初期登録して、先頭から始まる区間を数え落とさないようにします。負数を含むので sliding window は使えません。」
「区間和 → 累積和の差」という言い換えは、この先の配列・DP 系の問題でも繰り返し登場します。two-sum の「相方を Map で探す」と組み合わさっている構造に気づけると、パターンとして定着します。
STEPWISE HINTS
ヒント
01最初の一手
各位置までの累積和を考えます。2つの累積和の差が target なら、その間の区間が答えです。
02処理の組み立て
現在の累積和を prefix とすると、過去に prefix - target が何回あったかが、今の位置で終わる区間数です。
03コードの形
freq = Map([[0,1]]) から始める。prefix を更新し、freq.get(prefix-target) を答えに足してから、freq[prefix] を増やす。
AFTER ACCEPTED
解説
まずは自分の言葉で方針を説明し、コードに落としてみましょう。