ゼロから始めるLeetCode Day56 「1480. Running Sum of 1d Array」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day55「22. Generate Parentheses」
次回
ゼロから始めるLeetCode Day57 「35. Search Insert Position」

Twitterやってます。

問題

1480. Running Sum of 1d Array

難易度はEasy。
問題としては配列numsが与えられます。全ての数を足した数をリストで返してください、という問題です。

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

解法

いわゆる累積和の問題ですね。
この問題自体は理解しやすいのでどういったやり方で実装するのか、というところが重要であると思います。

実装についてはPythonの関数に詳しいかどうかで書き方が変わってくると思います。

例えば、itertools.accumulateを知っているならば以下のように書けます。

class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        return itertools.accumulate(nums)
# Runtime: 60 ms, faster than 33.33% of Python3 online submissions for Running Sum of 1d Array.
# Memory Usage: 14.1 MB, less than 33.33% of Python3 online submissions for Running Sum of 1d Array.

超簡潔に書けるので知っている、もしくは自由にドキュメントなどを調べられるような環境であればこちらを使えば良いでしょう。

しかし、忘れていた場合にゼロから考える場合にはどう書くのか、ということも念頭に置いておかなければなりません。

累積和についての考え方はけんちょんさんの

累積和を何も考えずに書けるようにする！

がとても読みやすくて理解がしやすいと思います。
読んでいて知ったのですが、AtCoaderなどでも累積和は応用範囲が広いんですね・・・

class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        i = 1
        while i<len(nums):
            nums[i] += nums[i-1]
            i += 1
        return nums
# Runtime: 44 ms, faster than 33.33% of Python3 online submissions for Running Sum of 1d Array.
# Memory Usage: 13.8 MB, less than 100.00% of Python3 online submissions for Running Sum of 1d Array.

今回はこのように書きました。

基本的な部分なのでこれくらいなら瞬殺できるくらいにしたいですね。

今回はここまで。お疲れ様でした。