【LeetCode】就活に向けたコーディングテスト対策 #01

#はじめに
こんばんは．
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にもあげておきます．

前回　次回