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

1) 問題概要

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

---

2) コード例

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 が再登場したら出現回数を追加）

最終的には、

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」 となる。