前からの合計と辞書で和がちょうど k になる区間を数える

配列とハッシュ問題 98

日ごとの増減の並びから、続いた日の合計がちょうど k になる区間の数を数えます。前からの合計を辞書に数えておき、「いまの合計から k を引いた値」が何回出たかを足していく、ハッシュの練習です。

海外で定番の問題リスト 4 本には入っていません

問題

小さなお店の、日ごとの売上の増減を表す整数の並び nums と、整数 k を受け取ります。続いた 1 日以上の区間で、増減の合計がちょうど k になる区間がいくつあるかを数えて返す関数を書いてください。

区間は、並びの中で途切れずに続いた部分です。飛ばして拾った組は数えません
始まりか終わりの位置が違えば、中身が同じでも別の区間として数えます
nums の長さは 1 以上 20000 以下です。値は -1000 以上 1000 以下で、負の数も 0 も入ります。k は -10000000 以上 10000000 以下です

入力と出力の例

例 1

合計が 3 になるのは、[3]、[-1, 3, 1]、[1, -2, 4]、[2, -1, 3, 1, -2] の 4 つです。

nums = [2, -1, 3, 1, -2, 4] k = 3

例 2

隣り合った 2 日の組は 3 つあり、どれも合計が 2 です。中身は同じでも、位置が違うので 3 つと数えます。

nums = [1, 1, 1, 1] k = 2

例 3

増えて減ってをくり返す並びです。合計が 0 になる区間は、隣り合った 2 日が 3 つと、4 日まるごとの 1 つで、4 つです。

nums = [5, -5, 5, -5] k = 0

面接での聞かれ方

面接では、並びと目標の値だけを渡されることがよくあります。

「和が k になる連続した部分配列の数を数えてください」
「負の数は入りますか？」と、自分から確かめるかを見られます
書き終えたあとに「全部が正の数なら、もっと記憶を減らせますか？」と広げられることもあります

負の数が入るかどうかで、使える型が変わります。全部が正なら窓を伸び縮みさせる書き方が使えますが、負の数があると窓を縮めても合計が減るとは限らないので、使えません。書く前に必ず確かめます。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「ハッシュマップ」に、この型の要点を表とコードでまとめています。

ハッシュは、値から番地を計算して、探す手間をほぼ 1 回にする仕組みです。重複や回数の問題は、この形で解けます。

まず考える手順

段 1

素直に書くなら、始まりの位置を全部試し、そこから終わりを 1 つずつ伸ばして合計を足していき、k になった回数を数えます。正しく動きますが、区間の数だけ手間がかかるので O(n²) です。長さ 20000 では 2 億回ほどになり、遅すぎます。

段 2

前からの合計を使います。位置 0 から i までの合計を s[i] とすると、i + 1 番目の日から j 番目の日までの区間の合計は s[j] - s[i] です。これが k になるのは、s[i] = s[j] - k のときです。

段 3

そこで、前から 1 つずつ読みながら、それまでに出た前からの合計の値を辞書に「何回出たか」で数えておきます。いまの合計 s に対して、s - k が辞書に何回あるかが、いまの日で終わる区間のうち合計が k になる物の数です。それを足してから、s を辞書に 1 回足します。

段 4

最初に、「まだ 1 日も足していない合計 0」を 1 回出たことにしておきます。こうしないと、1 日目から始まる区間を数え落とします。例 1 の [2, -1, 3, 1, -2] は、合計 3 から 3 を引いた 0 を探して見つかる区間です。

解答

Python

from collections import Counter


def count_sum_runs(nums, k):
    seen = Counter({0: 1})
    s = 0
    count = 0
    for x in nums:
        s += x
        count += seen[s - k]
        seen[s] += 1
    return count

JavaScript

function countSumRuns(
  nums,
  k
) {
  const seen = new Map();
  seen.set(0, 1);
  let s = 0;
  let count = 0;
  for (const x of nums) {
    s += x;
    const hit = seen.get(s - k);
    count += hit ?? 0;
    const n = seen.get(s) ?? 0;
    seen.set(s, n + 1);
  }
  return count;
}

Go

func countSumRuns(
	nums []int,
	k int,
) int {
	seen := map[int]int{0: 1}
	s := 0
	count := 0
	for _, x := range nums {
		s += x
		count += seen[s-k]
		seen[s]++
	}
	return count
}

s は、いまの日までの前からの合計です。足す順に気をつけます。先に s - k の回数を足し、あとで s を辞書に入れます。逆にすると、k が 0 のとき、長さ 0 の区間を 1 つ多く数えてしまいます。Python の Counter と Go の map は、無い鍵を 0 と読むので、そのまま足せます。

計算量

時間は O(n) です。並びを前から 1 回なめ、辞書を引くのも足すのも平均で一定の手間です
使う記憶は O(n) です。前からの合計は、多くて n + 1 通りの値が辞書に入ります
段 1 の全部試す書き方は、記憶は O(1) ですが、時間が O(n²) です

よくある間違い

窓を伸び縮みさせる書き方を使う。合計が k を越えたら左を縮める書き方は、全部が正の数のときだけ正しく動きます。例 3 のように負の数があると、縮めても合計が減るとは限らず、区間を数え落とします
辞書の最初に合計 0 を入れ忘れる。 1 日目から始まる区間が数えられません。例 2 なら、最初の [1, 1] を落として 2 を返します
辞書に入れてから回数を足す。 k が 0 のとき、いまの合計どうしを引いた「長さ 0 の区間」まで数えます。例 3 なら 4 ではなく 8 を返します
回数ではなく、出たかどうかだけを覚える。同じ前からの合計が何回も出る並び (例 3 や 0 が続く並び) で、区間を少なく数えます。辞書には回数を持たせます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def count_sum_runs(nums: list[int], k: int) -> int:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(count_sum_runs([2, -1, 3, 1, -2, 4], 3))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します