enumerate

はじめに

leetcodeの問題を解いていて解けたものの計算量がO(n^2)になってしまいました。
解説にO(n)のものがあり、enumerateを使っていて感動したので残しておきます。

enumerate

forループを使うとき引数にインテラブルオブジェクトを指定すると要素とindex番号を取得できる。

＊インテラブルオブジェクトとは、forループを使って取り出すようなオブジェクトのこと。
リスト、辞書、タプル、文字列など

enumerateの使い方は以下。

nums = [1, 10, 100]
for i, num in enumerate(nums):
    print(i, num)

実行結果は

0 1
1 10
2 100

使った結果

使う前はfor文の中にfor文を入れてこんな感じになってました。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        answer = []
        for i in range(len(nums)):
            target_copy = target - nums[i]
            for j in range(len(nums)-1):
                if j != i:
                    if nums[j] == target_copy:
                        answer.append(i)
                        answer.append(j)
                        return answer

enumerate、辞書を使うと以下のようになる。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        tmp = {}
        for i, num in enumerate(nums):
            target_copy = target - num
            if target_copy in tmp:
                return [tmp[target_copy], i]
            tmp[num] = i

実行速度がとても速くなりました。ただ、二つ目の方がメモリをたくさん使ってしまうらしい。

最後に

実行速度とメモリのバランスが難しいです。間違っている箇所があったら教えていただけると嬉しいです。