Description

Given an array nums.
We define a running sum of an array as runningSum[i] = sum(nums[0]…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[0] 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[0] + N[1] + N[2] to get the running-sum of N[2]. Instead, we just add N[2] to A[1] since A[1] already has sum of N[0] and N[1] during for-loop. N[2] also can be replaced with A[2] by initializing A[] with N[]. That is, N[0] + N[1] + N[2] == A[1] + N[2] == A[1] + A[2].

Reference

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