はじめに
こんばんは．
M1就活生がLeetCodeから，easy問題を中心にPythonを用いて解いていきます．
↓では，解いた問題のまとめを随時更新しています．
まとめ記事
問題
今回解いたのは，難易度easyから 問題1のTwo Sum です．
問題としては，整数numsの配列と整数targetが与えられたとき，numsの中から整数2つを選び，その合計がtargetと一致するインデックスを返すというもの．
なお，同じ要素は2度使えないとのこと．
Example 1：
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].
書いたコード
とりあえず，思いついたままに書いてみました．
class Solution():
def twoSum(self, nums, target):
for i in range(len(nums)):
for j in range(len(nums)):
if i == j:
continue
if nums[i] + nums[j] == target:
return [i, j]
うーん，何をやっているかはわかるものの，総当りでの解き方なので，実行時間がやはりかかってしまいます．
rangeをenumerateにしたり，内側のループは開始位置を変えてやればifが不要になるなど，まだまだ改良すべきところがありますね．
問題としては解けたのでとりあえずよしとします．
なお，LeetCodeには，ユーザーがそれぞれの言語で解法を投稿しています．
Python3を使ったコードで，パット見での評価が高そうなものとして以下がありました．
class Solution:
def twoSum(self, nums, target):
h = {}
for i, num in enumerate(nums):
n = target - num
if n not in h:
h[num] = i
else:
return [h[n], i]
なるほど．．ちょっとよくわからん．
3つほどヒントがあったので，大事そうな部分を読んでみます．
Hint 2:
So, if we fix one of the numbers, say
x
, we have to scan the entire array to find the next number
y
which is
value - x
where value is the input parameter. Can we change our array somehow so that this search becomes faster?
xを固定すると，targetと一致する組み合わせ(x,y)を全探索しないといけない．
このとき，yはvalue - xだよとのこと．
Hint 3:
The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?
なるほど，辞書を使えば効率よく書けるということか．
つまり，辞書にx = numを格納していき，y = target - xとなるようなyが辞書に存在していれば，その組み合わせのインデックスを返せば良いということですね．
おわりに
正直，解法を見ても頭でわからないことが多かったので，実際紙に書いて整理してました．
easy問題とはいえ，なかなか難しくないですか？（汗）
今回書いたコードはGitHubにもあげておきます．