【LeetCode】1.Two Sum　解答・解説【Python】

LeetCodeの問題を解きます。問題文は翻訳サイトと私の拙い英語力で和訳しており、正確でない可能性が高いためご注意ください。

問題文
1. 原文
2. 和訳
方針
解答
1. 解答1：Python, brute force
  1. コメント＋コード
  2. コードのみ
2. 解答2：Python, ハッシュテーブル
補足・参考・感想

問題文

原文

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

和訳

整数の配列numsと整数targetが与えられる。合計がtargetとなるような2つの数字のインデックスを返せ。

各入力は1つの解をもつと仮定して良よく、同じ要素を2回使ってはならない。

解答は任意の順番で返して良い。

方針

・全探索で解いてみます。

解答

解答1：Python, brute force

コメント＋コード

#クラス名を定義
class Solution:
    #関数を定義。numは要素がint型のリスト、targetはint型、返り値は要素がint型のリスト
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        #numsの要素数だけ繰り返す
        for i in range(len(nums)):
            #i+1からnumsの要素数まで繰り返す
            for j in range(i+1,len(nums)):
                #配列numのi番目と、j番目(つまりi+1)の和がtargetに等しい場合、
                if nums[i]+nums[j] == target:
                    #i,jを配列として返す
                    return [i,j]

#クラス名を定義

class Solution:

#関数を定義。numは要素がint型のリスト、targetはint型、返り値は要素がint型のリスト

def twoSum(self, nums: List[int], target: int) -> List[int]:

#numsの要素数だけ繰り返す

for i in range(len(nums)):

#i+1からnumsの要素数まで繰り返す

for j in range(i+1,len(nums)):

#配列numのi番目と、j番目(つまりi+1)の和がtargetに等しい場合、

if nums[i]+nums[j] == target:

#i,jを配列として返す

return [i,j]

コードのみ

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)):
                if nums[i]+nums[j] == target:
                    return [i,j]

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)):

if nums[i]+nums[j] == target:

return [i,j]

・時間計算量：O(n^2)

配列numsについて、全ての組み合わせを試す2重ループを行っている

・空間計算量：O(1)

計算結果を配列に記録するようなことがないため。

解答2：Python, ハッシュテーブル

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        #辞書型変数を用意。numsの値をキー、インデックスを値とする
        nums_dict = {}
        #iはnumsのインデックス、valueはnumsのi番目の要素の値
        for i, value in enumerate(nums):
            #diffはtargetからi番目の要素の値を引いた値
            #diff = target - nums[i]
            diff = target - value
            #diffが既に辞書に入っている場合
            if diff in nums_dict:
                #辞書の値からインデックスと、iをリストにして戻り値とする
                return [nums_dict[diff], i]
            #diffが辞書にない場合は、値をキー、インデックスを値として辞書に登録
            nums_dict[value] = i

class Solution:

def twoSum(self, nums: List[int], target: int) -> List[int]:

#辞書型変数を用意。numsの値をキー、インデックスを値とする

nums_dict = {}

#iはnumsのインデックス、valueはnumsのi番目の要素の値

for i, value in enumerate(nums):

#diffはtargetからi番目の要素の値を引いた値

#diff = target - nums[i]

diff = target - value

#diffが既に辞書に入っている場合

if diff in nums_dict:

#辞書の値からインデックスと、iをリストにして戻り値とする

return [nums_dict[diff], i]

#diffが辞書にない場合は、値をキー、インデックスを値として辞書に登録

nums_dict[value] = i

ハッシュテーブル、Pythonでは辞書型変数を使うことで、時間計算量を削減できる。

探索した要素と対になる値が辞書にあるかを判定し、あればそのインデックスと現在探索中のインデックスを返す。

無ければ、現在探索中の値をキー、そのインデックスを値として辞書に登録する。

・時間計算量：O(n)

探索済みの要素と対になる値を記録しておくことで、配列numsの走査が1回で済む。

・空間計算量：O(n)

探索済みの要素を記録している

補足・参考・感想

今回、あり得る組み合わせの全てを1つ1つ見た上で条件と合致するかを調べる解法にしています。このような解法は英語ではbrute forceと表現するようです。

indicesは日本語で言うインデックスのようです。

今回、初めてLeetCodeの問題を解いてみました。、Pythonで解答する際のエディタにクラスと関数の定義がデフォルトでセットされており、引数と返り値の型を指定するようになっているなど、Atcoderとはまた異なっています。

解答や解説、エディタにはデフォルトでC++が設定されているので、やはりC++の勉強は必須なのかもしれません。

英語で問題を読むという部分が既にハードルが高いですが、これから少しずつ挑戦していきたいと思います。

次の問題：9. Palindrome Number

記事一覧：LeetCode記事一覧