ゼロから始めるLeetCode Day33「1. Two Sum」

概要

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

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

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

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

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

Leetcode

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

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day32「437. Path Sum III」
次回
ゼロから始めるLeetCode Day34「118. Pascal’s Triangle」

問題

1. Two Sum

LeetCodeに登録した際に一番最初に解くであろう問題について書いてなかったので、今更ながら書きます。

難易度はEasy。
Top 100 Liked Questionsからの抜粋です。

問題としては、整数の入った配列と特定の値が格納された変数targetが与えられます。配列の中から二つの整数を選び、targetと一致する組み合わせを見つけ、配列のインデックスを返すような関数を実装してください。
なお、その組み合わせは一つしか存在せず、かつ同じ値を二度使うことは許されません。

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解法

例えば全探索で書いてみるとこうなります。

全探索とはいわゆるしらみつぶしに調べるようにする書き方で、全てのパターンを調べようとする代わりに致命的なパフォーマンスとなってしまうことがほとんどです。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                ans =  nums[i] + nums[j]
                if target == ans:
                    return [i,j]
# Runtime: 6848 ms, faster than 5.01% of Python3 online submissions for Two Sum.
# Memory Usage: 14.6 MB, less than 18.14% of Python3 online submissions for Two Sum.

遅いですね。
では代わりにハッシュマップを使って書いてみましょう。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        
        for i in range(len(nums)):
            num = nums[i]
            complement = target - num
            if num in hashmap:
                return [hashmap[num],i]
            else:
                hashmap[complement] = i
# Runtime: 52 ms, faster than 60.15% of Python3 online submissions for Two Sum.
# Memory Usage: 15.3 MB, less than 5.11% of Python3 online submissions for Two Sum.

かなり速度が改善されましたね。

言語の書き方について学んで短く書いたりするのも大切ですが、それだけではなく、書き方一つで速度を大幅に変えることができるというのがデータ構造とアルゴリズムを学ぶ大きな理由の一つと言えるでしょう。

自分への戒めのためにもここで書いておきます。

こっちの書き方の方が良いよ！とかこの言語で書いてみたよ！とかがあれば是非コメントしてみてください。