LeetCode Js-1480. Running Sum of 1d Array

    AllenLi
    LeetCode Js-Array

    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.

    給予一個 nums 的整數陣列，我們將加總的陣列定義為runningSum[i] = sum(nums[0]…nums[i])。
回傳 nums 的加總陣列。

                        V
ex.runningSum[i] = [1, 1+2]
                    i-1, i
- nums[0] ; i = 0
- runningSum[i - 1] + nums[i]) ; i > 0

- 1d Array = one-dimensional array = 一維陣列

    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:
    1. 先設定初始值為 currentSum = 0。
    2. 運用 for迴圈來將 nums 的陣列逐一計算。
    3. 每一輪都將 currentSum 加入當前的元素值 nums[i]。
    4. 並將 nums[i] 更新成加總後的 currentSum。
    5. 回傳新的 nums。

    Code 1: for loop BigO(n)

    var runningSum = function(nums) {
    let currentSum = 0
    for (i = 0; i < nums.length; i++) {
        currentSum += nums[i]
        nums[i] = currentSum
    }
    return nums
}

    FlowChart:
    Example 1

    Input: nums = [1,2,3,4]

step.1
i = 0
currentSum = 0
currentSum + nums[i] = 0 + 1 //1
nums[i] = currentSum //1

step.2
i = 1
currentSum = 1
currentSum + nums[i] = 2 + 1 //3
nums[i] = currentSum //3

step.3
i = 2
currentSum = 3
currentSum + nums[i] = 3 + 3 //6
nums[i] = currentSum //6

step.4
i = 3
currentSum = 6
currentSum + nums[i] = 6 + 4 //10
nums[i] = currentSum //10

return nums //[1, 3, 6, 10]

    Example 2

    Input: nums = [1,1,1,1,1]

step.1
i = 0
currentSum = 0
currentSum + nums[i] = 0 + 1 //1
nums[i] = currentSum //1

step.2
i = 1
currentSum = 1
currentSum + nums[i] = 1 + 1 //2
nums[i] = currentSum //2

step.3
i = 2
currentSum = 2
currentSum + nums[i] = 2 + 1 //3
nums[i] = currentSum //3

step.4
i = 3
currentSum = 3
currentSum + nums[i] = 3 + 1 //4
nums[i] = currentSum //4

step.5
i = 4
currentSum = 4
currentSum + nums[i] = 4 + 1 //5
nums[i] = currentSum //5

return nums //[1, 2, 3, 4, 5]

    Example 3

    Input: nums = [3,1,2,10,1]

step.1
i = 0
currentSum = 0
currentSum + nums[i] = 0 + 3 //3
nums[i] = currentSum //3

step.2
i = 1
currentSum = 3
currentSum + nums[i] = 3 + 1 //4
nums[i] = currentSum //4

step.3
i = 2
currentSum = 4
currentSum + nums[i] = 4 + 2 //6
nums[i] = currentSum //6

step.4
i = 3
currentSum = 6
currentSum + nums[i] = 6 + 10 //16
nums[i] = currentSum //16

step.5
i = 4
currentSum = 16
currentSum + nums[i] = 16 + 1 //17
nums[i] = currentSum //17

return nums //[3, 4, 6, 16, 17]

    Remark:
    使用雙「.map()」來建立一個新的陣列，並將其中各個元素分別做相同計算。
    Code 2: map BigO(n)

    var runningSum = function(nums) {
    let currentSum = 0
    return nums.map(num => currentSum += num)
};

    Code 3: for loop BigO(n)

    var runningSum = function(nums) {
    for (let i = 1; i < nums.length; i++) {
        nums[i] += nums[i - 1]
    }
    return nums
};

    Code 4: for loop BigO(n)

    var runningSum = function(nums) {
    let newNums = []

    for (let i = 0; i < nums.length; i++) {
        if (i === 0) {
            newNums[i] = nums[i]
        } else {
            newNums[i] = newNums[i - 1] + nums[i]
        }
    }
    return newNums;
}

    Code 5: forEach BigO(n)

    var runningSum = function(nums) {
  const runningArray = []
  nums.forEach((num, index) => {
      if (index === 0) {
          runningArray.push(num)
      } else {
          runningArray.push(runningArray[index - 1] + num)
      }
  })
  return runningArray;
};

    Code 6: map BigO(n)

    var runningSum = function(nums) {
  let sum = 0
  const runningMap = nums.map(num => {
    sum += num
    return sum
  });
  return runningMap;
};

    Code 7: reduce BigO(n)

    var runningSum = function(nums) {
  return nums.reduce((acc, num, i) => {
    if (i === 0) {
      acc.push(num);
    } else {
      acc.push(acc[i - 1] + num);
    }
    return acc;
  }, []);
};

    Code 8: recursion BigO(n)

    var runningSum = function(nums) {
    const array = []
    function Sum(number) {
       if (number === 0) {
           array.push(nums[number])
           return nums[number]
       } else {
           let sum = nums[number]+Sum(number-1)
           array.push(sum)
           return sum
       }
    }
    Sum(nums.length-1)
    return array
};

    Related Posts