Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

1480. Dynamic sum of one-dimensional arrays

The question to describe

Give you an array nums. RunningSum [I] = sum(nums[0]… Nums [I]).

Return the dynamic sum of NUMS.

Example 1:

Input: nums = [1, 2, 3, 4] output:,3,6,10 [1] : dynamic and calculation process of [1, 1 + 2, 1 + 2 + 3, 1 + 2 + 3 + 4].Copy the code

Example 2:

Output: input: nums =,1,1,1,1 [1] [1, 2, 3, 4, 5] : dynamic and calculation process of [1, 1 + 1, 1 + 1 + 1, 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1].Copy the code

Idea 1: Prefix sum

  1. fromi = 1To start, loop through the array
  2. Iterate directly to update the current number
  3. nums[i] = nums[i] + nums[i - 1]
  4. Finally, return the original arraynums
const runningSum = nums= > {
    const len = nums.length;
    for (let i = 1; i < len; i++) {
        nums[i] += nums[i - 1];
    }
    return nums;
};
Copy the code

Idea 2: Dynamically plan DP

Analysis: Use the idea of dynamic programming to process, storing the previous values in sequence.

var runningSum = function(nums) {
    let res = [];
    let len = nums.length;
    let dp = new Array(len).fill(0);

    dp[0] = nums[0]
    for(let i=1; i<len; i++) {
        dp[i] = dp[i-1] + nums[i] 
    }
    return dp;
};

Copy the code

Idea 3: Higher-order functions

The map version

Analysis: We all know that the map() method creates a new array and returns each element in the array as a return after calling the provided function once. Seek processing situation of the artifact.

var runningSum = function(nums) {
  let num = null;
  let result = nums.map((item) = > (num += item));
  return result;
};
Copy the code
Reduce version
var runningSum = function(nums) {
	let newNums = [];
	nums.reduce((pre, now, index) = >{
		newNums.push(pre);
		if(index === nums.length-1){
			newNums.push(pre + now);
		}
		return pre + now;
	},0);
	return newNums;
};
Copy the code

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤