Running Sum of an Array
整数の配列 nums が与えられます。同じ長さの新しい配列を返してください。その配列のインデックス i の要素は、左から最初の i+1 個の数を読み取った後の累計、つまり nums[0] + nums[1] + ... + nums[i] です。
関数
- numsinteger-array
- 左から右へ足し合わせる数
- 戻り値integer-array
- nums の各要素に対する累計
制約
1 ≤ nums.length ≤ 5000-104 ≤ nums[i] ≤ 104- すべての累計値は32ビット符号付き整数に収まります。
例
- 入力
- nums = [3, 1, 4, 1, 5]
- 出力
- [3, 4, 8, 9, 14]
- 説明
- 足し続けます。
3、次に3 + 1 = 4、4 + 4 = 8、8 + 1 = 9、そして9 + 5 = 14です。それぞれの合計は、最後に加えた数のインデックスに入ります。
- 入力
- nums = [-2, 5, -3]
- 出力
- [-2, 3, 0]
- 説明
- 負の数は合計を減らします。
-2、次に-2 + 5 = 3、そして3 + (-3) = 0。
- 入力
- nums = [7]
- 出力
- [7]
- 説明
- 単一の数値の累積合計はその数値自身なので、答えは
[7]です。
提出時に隠しテスト+13件
発展問題
各セルに、左上隅からそのセルまでの長方形の合計が入るようなグリッドを、同じように作れますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
インデックス
iの答えは、インデックスi-1の答えとどのように関連していますか？2つの合計の差は、ちょうど1つの数値
nums[i]です。先頭からの接頭辞を再び合計する必要はありません。変数
totalを1つ用意します。numsを左から右へ順に確認し、各数値をtotalに加算して、同じインデックスの答えにtotalを書き込みます。
解説
各回答はnumsの先頭部分の合計であり、隣り合う先頭部分は要素がちょうど1つだけ異なります。各先頭部分を最初から再計算すると、作業のほとんどが繰り返されます。一方、合計を引き継いでいけば、加算1回だけですべての回答を得られます。その結果が累積和配列で、高速な範囲和を実現する仕組みです。
各接頭辞の合計を最初から計算する
考え方
定義どおりに、一語一句そのまま実行します。各インデックス i について、合計を 0 で新しく始め、nums[0] から nums[i] までを加算して、その結果を保存します。[3, 1, 4, 1, 5] の場合、最後の答えでは5つすべての数を加算します。3 + 1 + 4 + 1 + 5 = 14。
これは正しい方法ですが、同じ処理を繰り返しています。インデックス4の合計は、インデックス3の合計 9 がすでに最初の4つの数の合計を保持しているにもかかわらず、nums[0] からやり直します。インデックス i では i+1 回の加算が必要なので、配列全体では 1 + 2 + ... + n = n(n+1)/2 回になります。n = 5000 の場合、約 1.25 × 10^7 回の加算になりますが、5000回で済むはずです。
返す必要がある答えの配列を除けば、保持するのは合計と2つのインデックスだけなので、追加の空間計算量は O(1) です。
アルゴリズム
- 長さが
nの回答配列を作成します。 - 各インデックス
iについて、total = 0を設定します。 0からiまでのすべてのjについて、nums[j]をtotalに加算します。- 回答のインデックス
iにtotalを格納し、最後のインデックスの後に回答を返します。
def runningSum(nums):
result = []
for i in range(len(nums)):
total = 0
for j in range(i + 1):
total += nums[j]
result.append(total)
return result累計を保持する
考え方
最初のi+1個の数の合計は、最初のi個の数の合計にnums[i]を加えたものです：result[i] = result[i-1] + nums[i]。したがって、1つ前より先までさかのぼることはありません。変数totalを1つだけ用意し、数を読み取るたびに加算して、新しい値を答えに書き込みます。
[3, 1, 4, 1, 5]の場合、totalは3、4、8、9、14となり、この5つの値が答えです。各要素は1回だけ読み取られ、加算も1回だけ行われるため、時間計算量はO(n)です。答えの配列を除けば、使用するメモリはtotalだけなので、追加の空間計算量はO(1)です。
ここでの合計は、どれも5000 × 10^4 = 5 × 10^7を超えず、32ビット整数に収まります。より大きな入力では、累積和はオーバーフローが起きやすい典型的なケースなので、64ビット整数の合計を使うのが安全です。
アルゴリズム
- 長さが
nの答えの配列を作成し、total = 0を設定します。 - インデックスを左から右へたどり、
nums[i]をtotalに加算します。 - 答えの配列のインデックス
iにtotalを書き込みます。 - 答えを返します。
def runningSum(nums):
result = []
total = 0
for num in nums:
total += num
result.append(total)
return result
落とし穴と境界ケース
ループには実際の処理が1行しかないため、間違いが起きるのは合計値をどこに置き、どこへ渡すかです。
- ループ内で
totalをリセットする。各答えがnums[i]だけになり、[3, 1, 4]は変更されずに返されます。 i = 0への対処なしにresult[i] = result[i-1] + nums[i]を使う。ほとんどの言語ではインデックス-1は範囲外です。Pythonでは最後の要素を指すため、0から始めるインプレース版では最後の数が最初の数に加算されます。- 最初の方法で内側のループを
j < iで止める。nums[i]が除外されるため、各答えは数が1つ足りません。 - コピーして答えを増やす。Rでは
result <- c(result, total)は各ステップでベクトル全体をコピーするため、高速な方法が再び二次時間になります。最初に全長分を確保してください。 - Cで
*returnSize = numsSizeを忘れる。これがないと、呼び出し元は合計値をいくつ読み取ればよいかわかりません。
よくある質問4
配列の累積和とは何ですか？
これは、最初の配列の同じ位置までの要素をすべて合計した値を各要素とする2つ目の配列です。接頭辞和または累積和とも呼ばれます。[3, 1, 4, 1, 5] の累積和は [3, 4, 8, 9, 14] です。
累積和を計算する時間計算量はどれくらいですか？
左から右へ合計を1つ累積していく方法は、各要素につき1回の加算で済むため、時間計算量は O(n) で、答え以外に必要な追加領域は O(1) です。各接頭辞を最初から再計算すると、n(n+1)/2 回の加算が必要になり、時間計算量は O(n²) になります。
累積和をインプレースで計算できますか？
はい。インデックス1から最後まで進み、nums[i] += nums[i-1]を設定します。nums[i-1]はすでにそれより前のすべての合計に変わっているため、各要素にはその時点までの累積和が入ります。入力以外の配列は使いませんが、元の値は失われます。
累積和は、範囲の合計に関するクエリにどのように役立ちますか？
累積和が求まったら、任意の区間 nums[l..r] の合計は prefix[r] - prefix[l-1] です。ただし l = 0 の場合は prefix[r] です。累積和が [3, 4, 8, 9, 14] のとき、インデックス 2 から 4 までの合計は 14 - 4 = 10 です。1 回の O(n) の走査の後は、各クエリを O(1) 時間で処理できます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def runningSum(nums):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums = [3, 1, 4, 1, 5]
期待値
[3, 4, 8, 9, 14]