問題
あるnums と、k をk 日のk 日の
- 幅は
いつも kで同じなので、 平均が いちばん 大きい所は、 合計が いちばん 大きい所と 同じです。 小数の 誤差を 持ち込まないように、 平均ではなく合計を 返します (平均が 欲しければ、 返した合計を kで割れば 求まります) kは 1 以上、numsの長さ以下です numsの長さは 1 以上 100000 以下、 値は どれも -10000 以上 10000 以下です
入力と出力の例
例 1
続いた 3 日の
入力
nums = [4, -1, 6, 2, -3, 5]
k = 3出力
9例 2
全部が
入力
nums = [-5, -2, -8, -1]
k = 2出力
-7例 3
k が
入力
nums = [3, 1, 2]
k = 3出力
6面接での聞かれ方
面接では、
- 「整数の
配列と k が あります。 長さ k の 連続した 部分で、 平均の 最大を 求めてください」 - 平均を
返す形で 聞かれたら、 「合計の 最大を 求めてから 最後に 1 回だけ k で 割ります」と 答えると、 割り算を 窓ごとに しないで済みます - 書き終えた
あとに 「長さが k 以上 なら 何でも よいとしたら？」と 続きを 聞かれる ことがあります。 これは 二分探索を 組み合わせる シニアの 問題に なるので、 ジュニアでは 考え方の 向きが 言えれば十分です
ジュニアの
アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。
まず
段 1
まずはk 個をk 回足すので、
段 2
隣り合う 2 つの
段 3
最初のk 個) だけは、k から
解答
Python
Python
def max_window_sum(nums, k):
total = sum(nums[:k])
best = total
n = len(nums)
for i in range(k, n):
total += nums[i]
total -= nums[i - k]
best = max(best, total)
return bestJavaScript
JavaScript
function maxWindowSum(nums, k) {
const n = nums.length;
let total = 0;
for (let i = 0; i < k; i++) {
total += nums[i];
}
let best = total;
for (let i = k; i < n; i++) {
total += nums[i];
total -= nums[i - k];
if (total > best) {
best = total;
}
}
return best;
}Go
Go
func maxWindowSum(
nums []int, k int,
) int {
total := 0
for i := 0; i < k; i++ {
total += nums[i]
}
best := total
n := len(nums)
for i := k; i < n; i++ {
total += nums[i]
total -= nums[i-k]
best = max(best, total)
}
return best
}nums[i] がnums[i - k] がi が k のnums[0] で、k までに
計算量
- 時間は O(n) です。
最初の 窓に k回、残りの n - k 個の 位置に 1 回ずつ足し 引きするので、 合わせて n 回です - 使う
記憶は O(1) です。 Python の 最初の sumは、先頭 k個の写しを 作ってから 足すので、 厳密には その間だけ O(k) 使います。 気になるなら JavaScript と 同じく 繰り返しで足します - 合計の
大きさは 最大で 10000 × 100000 で 10 億なので、 Go の int(64 ビット) でも JavaScript の数でも あふれません
よく
- 最長の
初めの 値を 0 にする。 例 2 のように 全部が 負の 数だと、 どの 窓も 0 より 小さいので、 0 が 返ってしまいます。 最初の 窓の 合計から始めます - 出る
数の 位置を 1 つずらす。 nums[i - k + 1]を引くと、 窓の 幅が 1 つ 縮みます。 「入る 位置から k 戻った 所が 出る 位置」と、 例 1 の 最初の ずらしで 確かめます - 窓ごとに
平均を 計算して比べる。 割り算の 誤差で、 同じはずの 値が 少し 違って 比べ間違える ことがあります。 合計で 比べ、 平均が 要るなら 最後に 1 回だけ割ります - 2 つ目の
繰り返しを k + 1から始める。 位置kの数が 入る 窓を 飛ばしてしまい、 例 1 では 2 つ目の 窓 (合計 7) を 見ないまま進みます
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「各位置から k 個を
足し直すと O(n × k) です。 隣の 窓とは 1 つ 入って 1 つ出るだけなので、 前の 合計に 入る 数を 足して 出る 数を 引けば O(1) で 更新できます。 幅が 同じなので、 平均が 最大の 所は 合計が 最大の 所です。 全体で 時間は O(n)、 記憶は O(1) です。」
書き終えたら、
「例 1 で
たどります。 最初の 窓は 4、 -1、 6 で 9 です。 次は 2 が 入って 4 が 出るので 7、 次は -3 が 入って -1 が 出るので 5、 最後は 5 が 入って 6 が 出るので 4 です。 いちばん 大きいのは 最初の 9 なので、 9 を 返します。」