This is the 28th day of my participation in the August Challenge

Leetcode -1480- Dynamic sum of one-dimensional arrays

[Blog link]

The path to learning at 🐔

The nuggets home page

[B].

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]. 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]. Example 3:

Input: nums = [3,1,2,10,1] output: [3,4,6,16,17]

Tip:

  • 1 <= nums.length <= 1000
  • -10^6 <= nums[i] <= 10^6

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1:

  • This problem is too easy to get wrong
  • Normal cycle evaluation can be
  • If you don’t want additional control variables, store them locally
class Solution { public int[] runningSum(int[] nums) { int n = nums.length; int[] ans = new int[n]; for (int i = 0, s = 0; i < n; i++) { ans[i] = s = s + nums[i]; } return ans; }}Copy the code
  • Time complexity O(n)
  • Space complexity O(N)

Idea 2: in situ replacement

  • Logic with space complexity O(1) is a local permutation
class Solution { public int[] runningSum(int[] nums) { for (int i = 1; i < nums.length; i++) { nums[i] += nums[i - 1]; } return nums; }}Copy the code
  • Time complexity O(n)
  • Space complexity O(1)
  • As an aside, the essence of this problem should be the basic process of solving prefix sums
  • I’m going to sum one of the subarrays in this scheme of summing up the first n terms
  • This is too easy to make sense of, okay
  • Si-Sj = a[I] +… +a[j]