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[] runningSum(int[] nums) {
for (int i = 1; i < nums.length; i++) {
nums[i] += nums[i - 1];
}
return nums;
}Time: O(n) · Space: O(1) extra (in-place)