※この記事は、Python利用者向けの記事です。
悩んでいる人
- 「Leetcodeで、『#1 Two Sum』を解いてみたけど、わからなかった」
- 「解答みても、英語でぜんぜんわからない」
- 「英語は多少できるけど、読むのがめんどくさい」
そんな悩みに答えます。
この記事では、Leetcodeの『#1 Two Sum』問題を解説します。
僕自身、現役SEですが、Pythonは全然触れたことありません。つまり、IT中級者ですが、Pythonは初心者です。
だから、Python初心者の気持ちが痛いほどわかる！
そんな僕が、TOEIC800オーバーの力を駆使して、初心者にもわかりやすく、日本語での解答解説をします。
ぜひ参考にしてください。
目次
Two Sumの問題
Two Sumの問題文 ※日本語訳つき
Given an array of integers nums and an integer target,
(整数のリストであるnumsと、整数であるtargetが与えられています。)return indices of the two numbers such that they add up to target.
(足してtargetの値になる、2つの整数をnumsからインデックス番号で返してください。)You may assume that each input would have exactly one solution,
(どの入力情報も1つの解答を持ち、)and you may not use the same element twice.
(同じ要素を2回使ってはいけません。)You can return the answer in any order.
(また、答えはどのような順番でも構いません。)
※以下、制約事項※
- 2 <= nums.length <= 105
- -109 <= nums[i] <= 109
- -109 <= target <= 109
- Only one valid answer exists.
(たった1つの適した解答が存在します。)
Two Sumの問題解説
まず、リスト、インデックス番号はそこそこ知っているものとします。
簡単に説明すると、
- リスト → 要素(数字とか文字)が複数入ったグループ
- インデックス番号 → 要素が、何番目にあるかを示す数字
という感じです。もっと知りたければ、ググりましょう。
わかりやすい記事が出てきます。
Two Sum問題で覚えておくことは、3つです。
- 整数値ではなく、インデックス番号を解答すること
- 解答するインデックス番号の順番は不問であること
- 必ず適した解が存在すること
では、さっそく解答にいきましょう。
Two Sumの解答
Solutionタブから、最も高評価な解答を紹介します。
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
h = {}
for i, num in enumerate(nums):
n = target - num
if n not in h:
h[num] = i
else:
return [h[n], i]
めちゃくちゃシンプルで、美しいですね・・・！
Two Sumの解法
とりあえずドキュメンテーション文字列
「ん？なにそれ？」と思ったあなた！
よくわかる･･･。
Pythonでは、慣習的に冒頭に説明文を書きます。それが、ドキュメンテーション文字列です。
解答でいうところの、以下です。
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
トリプルクォートで囲って、引数と返り値のくわしい情報を書きます。
今回は、numsがリスト、targetが整数、返り値がリストであることを明記します。
辞書を定義する
解答でいうところの、以下です。
h = {}
辞書を簡単に説明すると、キーワードに対応した要素を格納しておくものです。
リストに似ていますが、重複したキーワードが存在しないことや、記載方法が違います。
- リスト → 角カッコ([])で表す。[A,B,C,D]のような書き方
- 辞書 → 中カッコ({})で表す。{A:B,C:D}のような書き方
なぜ辞書を使うのか？
Two Sum問題で、一番難しいところです。
大事なことの1つめを思い出しましょう。
整数値ではなく、インデックス番号を解答すること
そうです。
要素ではなく、インデックス番号を解答します。
つまり、要素とインデックス番号の関係性がわかりやすいと、解答しやすいですよね。
そこで、辞書のキーワード→要素、キーワードに対応した要素→インデックス番号を格納します。
こうすることで、後々の処理が圧倒的に楽になります。
enumerate関数
はい、突然できてきました。謎の登場人物です。
ただし、実は超重要人物です。
というか、便利すぎるやつなんです。
1つの関数で、要素とインデックス番号を取得して、繰り返し(forループ)に利用できます。
まだPythonを学習して浅いですが、enumerate関数を目にした回数は異常です。
絶対に覚えておきましょう。
targetと要素の差をとる
n = target - num
enumerate関数で取得した要素numで、targetとの差をとります。
繰り返し(forループ)にいるので、numはループが繰り返すたびに、numsの次の要素になります。
例えば、numsが1，2，3，4という要素を持ったリストなら、
- 1回目のループ→ num=1
- 2回目のループ→ num=2
- 3回目のループ→ num=3
- 4回目のループ→ num=4
- 要素がないのでループ終了
という繰り返しです。
辞書hにnが存在しない場合の処理
解答でいうところのこちらです。
if n not in h:
h[num] = i
if文は条件分岐をするもので、条件A→処理B、条件Aではない→処理C、と分岐することができます。
ここでは、辞書hに差nが存在しないことを条件にしています。
ただ、この時気をつけることがあります。
辞書には、キーワードと要素がありましたよね？
ここで存在を確認するのは、キーワードの方です。
したがって、辞書のキーワードに、nがないことを確認します。
そして、nがなければ要素をキーワード、インデックス番号を要素として、辞書hに登録します。
- 要素 → 辞書のキーワードに格納
- インデックス番号 → 辞書の要素に格納
なぜこんなことをするかというと、リストに含まれる他の要素でtargetとの差nをだしたとき、差nがすでに辞書に存在するか、確認するためです。
大事なこと3つめを思い出しましょう。
必ず適した解が存在すること
必ず適した解があるので、総当たり的なやり方でも解答にたどり着くのです。
if条件以外の処理
条件分岐(if文)には、その他の条件で分岐させたり(elif文)、if条件以外で分岐すること(else文)ができます。
else:
return [h[n], i]
処理内容は簡単です。
eunumerate関数で取得した、インデックス番号i、要素numが手元にあります。
また、targetとnumの差nが、辞書hに存在することもわかっています。
なので、インデックス番号iと、辞書にキーワードnに対応して格納された要素h[n]を返します。
※辞書でキーワードに対応した要素を取り出す時は、角カッコで取得します。
ここで、大事なこと2つめを思い出しましょう。
解答するインデックス番号の順番は不問であること
順番は特に気をつけなくてもいいですね。
なので、そのままreturnして、処理完了です！
基本的ながら、考え方が難しい１問
お疲れ様でした！
使っている処理自体は、そこまで難しくなく、基本的なことです。
しかし、考え方が難しい１問でしたね･･･。
このレベルでeasyなのか･･･。
と思ったあなた！
わかる・・・。僕もめっちゃ思いました。
でも慣れたらこっちのもんですよ！
たくさん問いた後に、もう1回TwoSumに戻れば、びっくりするくらい簡単かもしれませんよ？
ではでは、次の問題でお会いしましょう。
