LeetCode - Running Sum of 1d Array

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.

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]

---

[일반적인 정답-98% faster]

class Solution {
    func runningSum(_ nums: [Int]) -> [Int] {
        var answer : [Int] = []
        var sum = 0
        for num in nums {
            sum += num
            answer.append(sum)
        }
        return answer
    }
}

---

[High Order Function 사용 - 98% faster]

class Solution {
    func runningSum(_ nums: [Int]) -> [Int] {
        var answer : [Int] = []
        var sum = 0
        nums.map {
            sum += $0
            answer.append(sum)
        }
        return answer
    }
}

---

[더 간단히 - 100% faster]

class Solution {
    func runningSum(_ nums: [Int]) -> [Int] {
        var sum = 0
        
        return nums.map{ (sum+=$0, sum).1 }
    }
}

• map 으로 iterate 하면서 튜플을 만든다. 튜플은 (sum+=$0, sum) 이다, 이중에 1번째를 리턴한다.
• (sum+=$0, sum).0 은 sum+=$0 이고 .1 은 sum
• 결국 이전 값을 다 더한 sum으로 새로운 배열을 만들어 리턴

---

[빠르진 않지만 한줄로 - 5.45% faster]

class Solution {
    func runningSum(_ nums: [Int]) -> [Int] {
        return nums.enumerated().map{ nums[0...$0.offset].reduce(0,+) }
    }
}

• 코드 이해하기 힘들다. 하나씩 떼서보자

for (n, c) in nums.enumerated() {
            print(n, c)
        }
//0 1
//1 2
//2 3
//3 4

print(nums.enumerated().map{ $0.offset})
 // [0, 1, 2, 3]
 
print(nums.enumerated().map{nums[0...$0.offset]})
// [ArraySlice([1]), ArraySlice([1, 2]), ArraySlice([1, 2, 3]), ArraySlice([1, 2, 3, 4])]

• enumerated().map{nums[0...$0.offset]} 으로 배열 nums에 대해 0, 01, 012, 0123 이런식으로 접근하는것 같다. 
• 여기에 reduce(0,+)를 통해 init value인 0으로 해서 각 값을 더한 값을 map 의 리턴으로 새로운 배열을 만든다.
• 내부적으로 for문 두개 도는거랑 비슷하다. 시간복잡도 O(N^2), 

---

[enumerated()]

Apple Developer Documentation

 

[High order function]

Higher Order Functions in Swift