LeetCode 560. 和がKの連続部分配列
この記事では、整数配列から和がKである連続部分配列の個数を数える方法を説明します。
1. 問題の理解
与えられた整数配列`nums`と整数`k`から、和が`k`である連続部分配列の個数を返す必要があります。
例
入力: nums = [1, 1, 1], k = 2
出力: 2
説明: [1,1]が2回出現（インデックス0~1と1~2）
2. 暴力的な解法
2.1 最も単純なアイデア
すべての連続部分配列を列挙し、その和を計算して`k`と等しいものを数えることができます。
int count = 0;
for (int i = 0; i < nums.length; i++) {
int currentSum = 0;
for (int j = i; j < nums.length; j++) {
currentSum += nums[j];
if (currentSum == k) {
count++;
}
}
}
**時間計算量**: O(n³)。この方法は効率的ではありません。
3. 最初の最適化: 前接和
3.1 前接和とは
前接和配列`prefixSums`を定義します。`prefixSums[i]`は`nums[0]`から`nums[i-1]`までの和を表します。
例:
nums = [1, 2, 3]
prefixSums = [0, 1, 3, 6]
部分配列`nums[i..j]`の和は`prefixSums[j+1] - prefixSums[i]`で計算できます。
3.2 前接和を用いた暴力的列挙
int[] prefixSums = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
prefixSums[i + 1] = prefixSums[i] + nums[i];
}
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i; j < nums.length; j++) {
if (prefixSums[j + 1] - prefixSums[i] == k) {
count++;
}
}
}
**時間計算量**: O(n²)。依然、長さの大きい配列ではタイムアウトする可能性があります。
4. 最後の最適化: 前接和 + ハッシュマップ
4.1 アイデアの転換
部分配列の和を`k`と等しくするためには、
`prefixSums[j+1] - prefixSums[i] == k`
を満足する`i`の数を数える必要があります。
この式は以下のように変形できます:
`prefixSums[i] == prefixSums[j+1] - k`
つまり、現在の`prefixSums[j+1]`に対し、`prefixSums[j+1] - k`が以前に何回出現したかを数えます。
4.2 前接和の出現回数を記録する
配列を走査しながら:
- 現在の前接和`sumSoFar`を計算します。
- `sumSoFar - k`が以前に何回出現したかをハッシュマップで確認します。
- 現在の前接和をハッシュマップに保存します。
4.3 代码実装
public int subarraySum(int[] nums, int k) {
// key: 前接和, value: 出現回数
Map sumCountMap = new HashMap<>();
sumCountMap.put(0, 1); // 初期状態: 前接和0が1回出現
int sumSoFar = 0;
int result = 0;
for (int num : nums) {
sumSoFar += num;
// sumSoFar - kが存在すれば、条件を満足する部分配列が存在します
if (sumCountMap.containsKey(sumSoFar - k)) {
result += sumCountMap.get(sumSoFar - k);
}
// 現在の前接和をハッシュマップに保存
sumCountMap.put(sumSoFar, sumCountMap.getOrDefault(sumSoFar, 0) + 1);
}
return result;
}
5. なぜこの方法は漏れがないのか?
例:
nums = [1, 2, -2, 1, -1], k = 1
前接和の変化:
0 → 1 → 3 → 1 → 2 → 1
最後の-1まで走査した時、`sumSoFar`は1です。`sumSoFar - k = 0`がハッシュマップに存在し、1回出現しています。これにより、配列の先頭から現在までの部分配列が条件を満足していることがわかります。
この方法は、**部分配列の終端を固定し、条件を満足する始点を迅速に探します**。
6. 計算量の分析
**時間計算量**: O(n)。配列を走査するだけで済みます。
**空間計算量**: O(n)。前接和を保存するためのハッシュマップが必要です。
7. 总结
| 方法 | 時間計算量 | 空間計算量 | 説明 |
|---|---|---|---|
| 暴力的列挙 | O(n³) | O(1) | 非効率的 |
| 前接和 + 双重ループ | O(n²) | O(n) | 依然、非効率的 |
| 前接和 + ハッシュマップ | O(n) | O(n) | 最適解 |
この方法の核心は、**空間を犠牲にして時間の節約を図る**ことです。具体的には、ハッシュマップを用いて条件を満足する前接和を迅速に探します。
8. 他の問題への応用
この問題の解法は、以下のような問題でも役立ちます:
- LeetCode 525. 最大1の連続部分配列
- LeetCode 974. 和がKで割り切れる部分配列