Running Sum of an Array
整数の配列 nums が与えられます。同じ長さの新しい配列を返してください。その配列のインデックス i の要素は、最初の i+1 個の数の合計である nums[0] + nums[1] + ... + nums[i] です。
関数
- numsinteger-array
- 左から右へ順に足し合わせる数
- 戻り値integer-array
- nums の各要素に対する累積合計（各要素につき1つ）
制約
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]
- 説明
- 1つの数値には、その数値自体という1つの累計しかないため、答えは
[7]です。
発展問題
各セルに、左上隅からそのセルまでの長方形の合計が入るグリッドについて、同じものを作れますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
インデックス
iの答えは、インデックスi-1の答えとどのように関連していますか？2つの合計は、
nums[i]という1つの数だけ異なります。先頭からのプレフィックスをもう一度合計する必要はありません。変数
totalを1つ用意します。numsを左から右へ順に見て、それぞれの数をtotalに加え、同じインデックスの答えにtotalを書き込みます。
解説
各答えはnumsの先頭部分の合計であり、隣り合う先頭部分は1つの要素だけ異なります。各先頭部分を最初から再計算すると、作業のほとんどを繰り返すことになります。代わりに合計を1つ保持して引き継げば、各答えに必要なのは1回の加算だけです。
各接頭辞を最初から合計する
考え方
定義に従います。各インデックス i について、合計を0で初期化し、nums[0] から nums[i] までを加算して、その値を格納します。各答えが定義どおりに計算されるため、これは正しい方法です。
インデックス i では i+1 回の加算が必要なので、配列全体では n(n+1)/2 回の加算が必要です。n = 5000 の場合、約 1.25 × 10^7 回の加算となり、5000で十分です。
アルゴリズム
- 長さが
nの回答配列を作成します。 - 各インデックス
iについて、total = 0を設定します。 0からiまでのすべてのjについて、nums[j]をtotalに加算します。totalを回答のインデックスiに格納し、最後のインデックスの後に回答を返します。
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]の場合、合計は3、4、8、9、14となり、これが答えです。
各要素につき加算は1回なので、時間計算量はO(n)、答え以外に必要な追加領域はO(1)です。
アルゴリズム
- 長さが
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
落とし穴と境界ケース
- ループ内で
totalをリセットする。どの答えもnums[i]だけになり、[3, 1, 4]は変更されずに返されます。 i = 0のときにresult[i-1]を読み取る。ほとんどの言語では範囲外になります。Pythonでは最後の要素が読み取られるため、インプレース版では最後の数値が先頭に加算されます。- ブルートフォース版の内側のループを
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つ持ち運ぶことで、時間計算量はO(n)となり、答え以外の追加の領域はO(1)です。各接頭辞を最初から再計算すると、時間計算量は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 です。O(n) の走査を1回行った後は、各クエリを O(1) で処理できます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def runningSum(nums):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums = [3, 1, 4, 1, 5]
期待される出力
[3, 4, 8, 9, 14]