[LeetCode/Swift] 1480. Running Sum of 1d Array

💡 문제 (Easy)

Running Sum of 1d Array - LeetCode

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의 러닝 합을 반환하세요.

 

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]

 

Constraints:

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

👩🏻‍💻 해결

1차 : 출력 배열을 선언하여 풀이시간 복잡도 O(n), 공간 복잡도 O(n)

class Solution {
    func runningSum(_ nums: [Int]) -> [Int] {
        var results: [Int] = []
        var sum: Int = 0

        for n in nums {
            sum += n
            results.append(sum)
        } 
        
        return results
    }
}

 

2차 : in-place 풀이

• in-place 알고리즘 : n 길이의 리스트가 있고, 이 리스트를 정렬할 때 추가적으로 메모리 공간을 할당하지 않아도 정렬이 이뤄지는 것

시간 복잡도 O(n), 공간 복잡도 O(1)

class Solution {
    func runningSum(_ nums: [Int]) -> [Int] {
        var nums = nums
        for i in 1..<nums.count {
            nums[i] += nums[i - 1]
        }

        return nums 
    }
}