累積和とハッシュマップで部分数列の和を見つける方法

## 1) 問題概要

- **問題**: 与えられた整数配列 `nums` の中で、「連続部分配列の合計」が特定の値 \(m\) になる場合が何個あるかを数え上げる。  
- **アプローチ**:  
  1. **累積和(prefix sum)** を使う。  
  2. 「過去に（現在の累積和 \(-\) \(m\)）という値がいくつ出現していたか」を素早く探す。  
  3. その出現回数だけ答えに加算すれば、連続部分配列の合計が \(m\) になる総数を得られる。

---

## 2) コード例

```java
import java.util.HashMap;

class Solution {
    public int solution(int[] nums, int m) {
        int answer = 0;
        int sum = 0;  // 現在までの累積和 (prefix sum)

        // map: 「ある累積和が何回現れたか」を記録する
        HashMap<Integer, Integer> map = new HashMap<>();
        // 累積和が0（何も足していない状態）が1回あったとみなす
        // → これにより、最初の要素までの合計が m のときにも対応可能
        map.put(0, 1);

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];                // 現在の要素を足して累積和を更新

            int target = sum - m;         // 「現在の累積和 - m」
            if (map.containsKey(target)) {
                // 過去に (sum - m) という累積和が存在したなら、
                // その回数だけ「いま i を終端とする部分配列」の合計が m になる
                answer += map.get(target);
            }

            // 現在の累積和 sum を map に登録（出現回数を1増やす）
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }

        return answer;
    }

    public static void main(String[] args) {
        Solution T = new Solution();
        System.out.println(T.solution(new int[]{2, 2, 3, -1, -1, -1, 3, 1, 1}, 5));
        System.out.println(T.solution(new int[]{1, 2, 3, -3, 1, 2, 2, -3}, 5));
        System.out.println(T.solution(new int[]{1, 2, 3, -3, 1, 2}, 3));
        System.out.println(T.solution(new int[]{-1, 0, 1}, 0));
        System.out.println(T.solution(new int[]{-1, -1, -1, 1}, 0));
    }
}
```

---

## 3) なぜ `sum - m` を確認するのか？

```
prefixSum[j] - prefixSum[i-1] = m 
prefixSum[i-1] = prefixSum[j] - m
```

- prefixSum[j]は、インデックス \(0\) から \(j\) までの累積和（コードでは `sum`）。
- 過去（インデックス \(0\) ～ \(j-1\) の範囲）で累積和が「prefixSum[j] - m」だった場所 (i-1）が存在すれば、そこから現在の \(j\) まで足し合わせた合計が \(m\) になる。

つまり、**「現在の `sum` - \(m\)」という値が過去の累積和として何回出現していたか** がわかれば、その回数だけ「今のインデックス \(j\) を終端とする部分配列の合計が \(m\) になる」ことを意味します。

---

## 4) 図・例での理解

### 例: 配列
nums = [2, 3, -1, 2],  m = 4

- 「連続部分配列の合計が 4 となるケースの数」を求める。

#### (1) すべて列挙（ブルートフォース的確認）
- `[2, 3, -1]` の合計 = 4  
- `[3, -1, 2]` の合計 = 4  
⇒ 計 2 個

#### (2) 累積和テーブル

| インデックス(i) | nums[i] | \(\text{prefixSum}[i]\) = 累積和 |
|:--------------:|:-------:|:--------------------------------:|
| 0              | 2       | 2                                |
| 1              | 3       | 5 （2 + 3）                     |
| 2              | -1      | 4 （5 + (-1)）                   |
| 3              | 2       | 6 （4 + 2）                      |

#### (3) コード上のロジック（ループ）の追跡

1. **初期状態**: `sum = 0`, `map = {0=1}`  
   - 「累積和が 0」の状態が 1 回あるとみなす（何も加算していない状態）

2. **i = 0**  
   - `sum = 0 + 2 = 2`  
   - `target = sum - m = 2 - 4 = -2`  
   - `map.containsKey(-2)` → ない  
   - `map.put(2, 1)` → map = {0=1, 2=1}  
   - `answer = 0`  

3. **i = 1**  
   - `sum = 2 + 3 = 5`  
   - `target = 5 - 4 = 1`  
   - `map.containsKey(1)` → ない  
   - `map.put(5, 1)` → map = {0=1, 2=1, 5=1}  
   - `answer = 0`  

4. **i = 2**  
   - `sum = 5 + (-1) = 4`  
   - `target = 4 - 4 = 0`  
   - `map.containsKey(0)` → ある（value=1）  
   - ⇒ `answer += 1` → `answer = 1`  
   - `map.put(4, 1)` → map = {0=1, 2=1, 5=1, 4=1}  
   - ここで「過去に累積和が 0 だった地点」から i=2 までの合計が 4 となる → `[2, 3, -1]`

5. **i = 3**  
   - `sum = 4 + 2 = 6`  
   - `target = 6 - 4 = 2`  
   - `map.containsKey(2)` → ある（value=1）  
   - ⇒ `answer += 1` → `answer = 2`  
   - `map.put(6, 1)` → map = {0=1, 2=1, 5=1, 4=1, 6=1}  
   - ここで「過去に累積和が 2 だった地点」（i=0）以降から i=3 までの合計が 4 → `[3, -1, 2]`

> 最終的に `answer = 2`。これは手動で列挙したときの結果（2 個）と一致します。

---

## 5) まとめ

1. **累積和(prefix sum)**  
   - 各インデックス i に対して、要素を足し込んでいき `sum` を更新する  
2. **HashMap** の利用  
   - key: ある累積和の値  
   - value: その累積和がこれまで何回登場したか  
3. 現在の累積和を `sum` とするとき、  
   target = sum - m
   が過去に何回登場したかを調べ、その回数だけ「連続部分配列の合計が \(m\) になる」ケースが存在するとみなせる  
4. その後、現在の `sum` も map に記録（もし同じ `sum` が再登場したら出現回数を追加）

最終的には、
```java
if (map.containsKey(sum - m)) {
    answer += map.get(sum - m);
}
map.put(sum, map.getOrDefault(sum, 0) + 1);
```
という処理で、  
「`prefixSum[j] - m = prefixSum[i-1]` をみたす i-1 がどれだけあるか」  
を即座に数えて、答え (`answer`) を更新していくわけです。

---

### ポイント（要約）
> **「今の累積和(sum) から m を引いた値(sum - m)」が、過去の累積和として何回現れているか**  
> → **その回数分だけ、「現在のインデックスで終わる区間の合計 = m」** となる。