基本資訊

• 難度： Easy
• 網址： https://leetcode.com/problems/running-sum-of-1d-array/

資料結構與演算法

• Prefix Sum

題意

給予一個整數陣列 nums ，請回傳每個位置的 running sum

Running Sum 的定義

runningSum[i] = sum(nums[0]…nums[i])

也就是位置 i 的值，會是從 0 到 i 的加總

另外暫存 sum 值

宣告一個 sum 在走訪過程中暫存總和，這樣子邊走訪就可以快速計算好 running sum 了。

程式碼

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

執行結果

• Runtime: 9 ms (Beats 95.21%)
• Memory: 14.2 MB (Beats 26.25%)

複雜度分析

令 n 為陣列的長度

複製原始陣列

這個方法直接複製一個 array 出來，從第 [1] 個位置開始走訪的最後

Routine

當走到 n 的時候，將前一個元素跟當前的元素加總，就會是 running sum 。

由於前一個元素一定會是 running sum ，因此能夠這樣子計算。

nums[n] += nums[n - 1]

程式碼

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

執行結果

• Runtime: 9 ms (Beats 95.21%)
• Memory: 14.02 MB (Beats 65.63%)

複雜度分析

令 n 為陣列的長度

結語

兩者的差別其實並沒有很大。雖然是推測，第二個雖然看起來比較單純，不需要另外宣告 sum ；但是根據過去經驗像是 複製整個陣列 和 變更陣列的值 的行為會拖慢執行時間，相較於 append ，後者會快很多。

以上，就是今天的 LeetCode in Swift ，

如果有什麼問題和回饋歡迎留言一起討論，今天就到這裡，明天見！