Given an array nums, return the running sum, where runningSum[i] = sum(nums[0]...nums[i]).
Example 1
Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: runningSum = [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: Each step adds exactly 1.
1 <= nums.length <= 1000-10^6 <= nums[i] <= 10^6This is the prefix sum concept in its most literal form — the output array IS the sequence of prefix sums.
You don't need a separate output array allocated up front and filled in a second pass — you can build it in place.
Each output value only depends on the previous output value plus the current input — one running total, one pass.
public int[] runningSumBruteForce(int[] nums) {
int[] result = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = 0; j <= i; j++) sum += nums[j]; // resum from scratch for every output position
result[i] = sum;
}
return result;
}Time: O(n^2) · Space: O(n) for the output array