部分配列の和 = k の個数
部分配列の和 = k の個数
このレッスンで分かること
- 配列
numsの中から「和がkちょうどになる 連続する部分配列」が何個あるかを数える問題は、競技プログラミングや面接でも頻出の良問です- 関数
subarraySumEqualsK(nums, k)は次を満たします- 各始点
iから右へ伸ばしながら和を更新するので、3 重ループを避けつつO(n^2)です
部分配列の和 = k の個数 とは
整数配列と
kを受け取り、和がkになる 連続する部分配列 の個数をhashmapと累積和でO(n)で数える。
配列 nums の中から「和が k ちょうどになる 連続する部分配列」が何個あるかを数える問題は、競技プログラミングや面接でも頻出の良問です。素朴に書くと O(n^2) か O(n^3) になりますが、累積和 と hashmap を組み合わせると O(n) に落とせます。前レッスンの two sum の応用編という位置づけです。
「区間の和」は累積和の差で表せる。差分を
hashmapで数えるとtwo sum風にO(n)で解ける。
仕様
関数 subarraySumEqualsK(nums, k) は次を満たします。
- 整数配列
numsと整数kを受け取る - 連続する部分配列のうち、和が
kになるものの 個数 を返す - 部分配列は
nums[i..j](0 <= i <= j < n) で、長さは 1 以上 - 同じ和の出現箇所が複数あれば、それぞれ別カウント
素朴な O(n^2) 解
Python
def subarraySumEqualsK(nums, k):
n = len(nums)
count = 0
for i in range(n):
s = 0
for j in range(i, n):
s += nums[j]
if s == k:
count += 1
return count各始点 i から右へ伸ばしながら和を更新するので、3 重ループを避けつつ O(n^2) です。中規模 (~ 10000) ならこれでも動きます。
O(n) アルゴリズム
累積和 prefix[i] = nums[0] + nums[1] + ... + nums[i-1] を考えると、nums[i..j] の和は prefix[j+1] - prefix[i] です。これが k になる条件は prefix[j+1] - prefix[i] == k、つまり prefix[i] == prefix[j+1] - k。
右端 j+1 まで走査したとき、「prefix[j+1] - k という累積和が左に何回現れたか」を hashmap で数えれば、その回数だけ条件を満たすペアがあると分かります。
図のポイント (テキスト併記)
prefix[0] = 0を最初に登録しておくのがコツです (空のプレフィックス分)
prefix[0] = 0 を最初に登録しておくのがコツです (空のプレフィックス分)。これを忘れると「nums[0..j] の和がそのまま k」のケースを 1 回数え漏らします。
Python での実装
Python
def subarraySumEqualsK(nums, k):
count = 0
prefix = 0
seen = {0: 1} # prefix が 0 の状態を 1 回登録 (空区間)
for v in nums:
prefix += v
need = prefix - k
count += seen.get(need, 0)
seen[prefix] = seen.get(prefix, 0) + 1
return countJavaScript での実装
JavaScript
function subarraySumEqualsK(nums, k) {
let count = 0;
let prefix = 0;
const seen = new Map();
seen.set(0, 1);
for (const v of nums) {
prefix += v;
const need = prefix - k;
count += seen.get(need) || 0;
seen.set(prefix, (seen.get(prefix) || 0) + 1);
}
return count;
}Java での実装
Java
import java.util.*;
public class Solution {
public static int subarraySumEqualsK(int[] nums, int k) {
int count = 0;
int prefix = 0;
Map<Integer, Integer> seen = new HashMap<>();
seen.put(0, 1);
for (int v : nums) {
prefix += v;
int need = prefix - k;
count += seen.getOrDefault(need, 0);
seen.put(prefix, seen.getOrDefault(prefix, 0) + 1);
}
return count;
}
}Go での実装
Go
func subarraySumEqualsK(nums []int, k int) int {
count := 0
prefix := 0
seen := map[int]int{0: 1}
for _, v := range nums {
prefix += v
need := prefix - k
count += seen[need]
seen[prefix]++
}
return count
}よくある間違い
1 つ目は seen[0] = 1 の初期化忘れ。これがないと、nums[0..j] の和がちょうど k の場合を数えられません。
2 つ目は 登録順。count += seen[need] を計算する 前 に prefix を seen に入れてしまうと、同じインデックスを 2 回使ったケースを誤って数えます。
3 つ目は 負の数 / ゼロ の扱い。配列に負の値が混ざっていても、累積和ベースなので問題なく動きます。スライディングウィンドウだと負の値で破綻するので、こちらの方が汎用的です。
累積和 +
hashmapは「区間の和 / 差 / 個数」をO(n)で解くための鉄板テクニック。
やってみよう
nums = [1, 1, 1], k = 2で答えが2になるか確認する ([1,1]が 2 か所)。- 部分配列の 個数 ではなく 最長の長さ を返すバージョンを書いてみる。
seenには「最初に prefix が出た index」を入れるのがコツ。 - 配列を 円環 にして、回り込む部分配列も数えるバリエーションも考えてみる。
1 つの問題を
O(n^2)からO(n)に落とす経験は実務でもよく効く。
よくある質問
Q. この内容は面接でよく聞かれますか？
A. コーディング面接の頻出範囲です。データ構造（リンクリスト・ツリー・グラフ）とアルゴリズム（DP・BFS/DFS）は IT 系大手の選考でほぼ確実に問われます。LeetCode の Top 100 にも該当問題が多数含まれます。
Q. 計算量と空間計算量はどっちを優先しますか？
A. 通常は時間計算量を優先し、空間が制約条件として明示されたら空間も考慮します。例えば「O(1) 空間で」と書かれていれば in-place アルゴリズム必須です。実務では時間 vs メモリのトレードオフを意識しつつ、ボトルネックを実測してから判断します。
Q. 問題が解けないときどう取り組めば良いですか？
A. まず小さな入力（n=3 程度）で手計算し、規則性を見つけます。次にナイーブ解（O(n²) でも可）を書き、最後に最適化します。いきなり最適解を狙うと手が止まりやすいので、段階的に進めるのが定石です。
次のレッスン
次は 最長連続部分列 で、最長連続部分列 を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 部分配列の和 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 部分配列の和 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 累積和 +
hashmapを使いO(n)で実装する - 配列に負の数や 0 が含まれても正しく動作すること
- 戻り値は部分配列の個数 (int)
入出力例
test-cases.txt
subarraySumEqualsK([1,1,1], 2) → 2
subarraySumEqualsK([1,2,3], 3) → 2
subarraySumEqualsK([1,-1,1,-1,1], 0) → 6
subarraySumEqualsK([3,4,7,2,-3,1,4,2], 7) → 4
subarraySumEqualsK([1], 0) → 0
subarraySumEqualsK([0,0,0], 0) → 6