Running Sum of 1d Array

tags: Easy

出題者 : 曾致銘

Problem

給定一個整數 length 和一個長度為 length 的整數陣列 nums。我們定義一個數字陣列的「動態和」為滿足 runningSum[i] = nums[0] + nums[1] + ... + nums[i]。請回傳 nums 的動態和。

Examples

範例 1：

輸入: 4 1 2 3 4
輸出: 1 3 6 10
解釋: 動態和計算過程為 1, 1+2, 1+2+3, 1+2+3+4

範例 2：

輸入: 5 1 1 1 1 1
輸出: 1 2 3 4 5
解釋: 動態和計算過程為 1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1

範例 3：

輸入: 5 3 1 2 10 1
輸出: 3 4 6 16 17
解釋: 動態和計算過程為 3, 3+1, 3+1+2, 3+1+2+10, 3+1+2+10+1

Constraints

• $1\le$ length
  $\le 1000$
• $-{10}^6\le$ nums[i]
  $\le {10}^6$

Hints

Hint 1

請思考要如何通過前一個動態和來計算當前的動態和 ?

Solution

Description

Approach 1: 創建另一陣列作為輸出

思路

我們需要算出 nums[i] 的動態和，其中 i 為從 0 到 length - 1 的整數且 length 是該陣列的長度。計算方法即為 nums[0] 到 nums[i] 的全項總和。我們可以創建一個相同長度的陣列作為輸出，並從第 0 項開始計算。在這種情況下，對於第 i 項元素，我們皆已經計算出其前一項的動態和，即 nums[0] 到 nums[i - 1] 的全項總和。因此，與其每一項都從頭開始計算其動態和，不如直接把該項加上已算好的前一項的動態和來的快速。

算法

1. 創建一長度為 length 的陣列 result。
2. 把 result[0] 的值設為 nums[0] 的值。
3. 把 result[i] 的值設為 nums[i] + result[i-1] 的值。
4. 重複步驟 3 直至 i 到達 length-1。

// 以下省略 cin 與 cout，僅呈現演算法部分
// 步驟 1
int result[length];
// 步驟 2
result[0] = nums[0];

for (int i = 1; i < length; i++) {
    // 步驟 3
    result[i] = result[i - 1] + nums[i];
}

複雜度分析

• 時間複雜度:
  $O(n)$ 其中
  $n$ 為輸入陣列的長度。這是由於我們使用了一個遍歷輸入陣列的迴圈所致。
• 空間複雜度:
  $O(1)$ 因為我們並沒有使用額外空間來「計算」。註：作為輸出和輸入的空間不納入計算空間複雜度的考量。

Approach 2: 把輸入陣列當作輸出使用

思路

在上一個層級中我們額外創建了一個陣列作為輸出。然而其實不用。我們可以對輸入陣列做一模一樣的計算且獲得相同的結果。

算法

1. 把 nums[i] 加上 i-1 項的動態和，而 i-1 項的動態和即被存在 nums[i-1]。
2. 重複步驟 1 直至 i 到達 length-1。

// 以下省略 cin 與 cout，僅呈現演算法部分
for (int i = 1; i < length; i++) {
    // 步驟 1
    nums[i] += nums[i - 1];
}

複雜度分析

• 時間複雜度:
  $O(n)$ 其中
  $n$ 為輸入陣列的長度。
• 空間複雜度:
  $O(1)$ 因為我們並沒有使用額外空間來「計算」。註：作為輸出和輸入的空間不納入計算空間複雜度的考量。

完整解答

#include <iostream>
using namespace std;

int main() {
    int length;
    cin >> length;
    int nums[length];
    
    for (int i = 0; i < length; i++) {
        cin >> nums[i];
        if (i > 0) {
            nums[i] += nums[i - 1];
        }
    }
    
    for (auto num : nums) {
        cout << num << " ";
    }
    
    cout << endl;
}

Reference

https://leetcode.com/problems/running-sum-of-1d-array/