# 리트코드 1480번 - Running Sum of 1d Array

zionhann·2022년 9월 28일
0 # Description

Given an array nums.
We define a running sum of an array as runningSum[i] = sum(nums…nums[i]).
Return the running sum of nums.

# Examples

Example 1:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].
Example 2:

Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]
Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].
Example 3:

Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]

# Solution

class Solution {
public:
vector<int> runningSum(vector<int>& nums) {
vector<int> ans(nums);

for (int i = 1; i < nums.size(); ++i) {
ans[i] = ans[i-1] + ans[i];
}
return ans;
}
};

# Explanation

## Pseudocode

procedure runningSum(N[])
A[] := N[]

for i := 1 to size of N[] do
set A[i] to A[i-1] + A[i]
end for

return A[]
end procedure
1. Initialize an integer vector A with given array N.
2. For each element in A, assign sum of (i-1)th element and itself.
3. Return the vector A.

## Why A[i]:=A[i-1]+A[i]?

Because A[i-1] contains sum of N to N[i-1].
Let an integer vector N be [1, 2, 3], then running-sum of this vector N is [1, 1+2, 1+2+3]. We don't need to add all of elements in N such as N + N + N to get the running-sum of N. Instead, we just add N to A since A already has sum of N and N during for-loop. N also can be replaced with A by initializing A[] with N[]. That is, N + N + N == A + N == A + A.

# Reference

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