LeetCode0001

LeetCodeでpythonを学んでみようと思いました。頑張ります。

Two Sum

https://leetcode.com/problems/two-sum/description/

Solution

Solution1 Brute Force

ブルートフォースで見つけるやつです。
二重for文でぶん回すだけ。
Pythonはlenで配列の大きさを求めて、range(n)で0:n-1のものとなる。
二つの数値を足した値がtargetになればいいので、重複を避けるために二つ目のfor文はrange(i+1,n)とする。
とはいえ、O(n^2)の計算量ではありますね。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n=len(nums)
        for i in range(n):
            for j in range(i+1,n): 
                if nums[i]+nums[j]==target:
                    return [i,j]

Solution2

辞書を使った方法。
dictの使い方はkeyと値を入れること。
hashmap={}としたときに
hashmap[key]=valueで、入れる
hashmap[key]でvalueにアクセスできる
足してtargetになる値としてkeyを持つ配列の添え字を調べており、
if文の条件式を少し見ると、comp in hashmapを用いて、辞書hashmapの中にcompというkeyが存在するかと、hashmap[comp]!=iで、自分自身を除外している。そして、i自体が添え字、hashmap[comp]が添え字となるので、以下のようになる。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap={}
        n=len(nums)
        for i in range(n):
            hashmap[nums[i]]=i
        for i in range(n):
            comp = target - nums[i]
            if comp in hashmap and hashmap[comp]!=i:
                return [i,hashmap[comp]]
        return []

Approach 3 One-pass Hash table

同様に、hashmap={}で空の辞書を作って、
ターゲットになりえる値を求めておく。
次にhashmapの中にcompとなりえる値があるかどうかを見る。
もしいれば、return [i,hashmap[comp]]でreturn
いなければ、今のiでの値をhashmapに登録する。
hashmap[num[i]]=i

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap={}
        n=len(nums)
        for i,v in enumerate(nums):
            comp=target-v
            if comp in hashmap:
                return [i,hashmap[comp]]
            hashmap[nums[i]]=i
        return []