LeetCode: Two Sum

LeetCodeで取り組んだ問題の備忘録です。

問題

変数nums（リスト型、int）及び変数target（int）を入力し、2つの数の合計がtargetとなるnumsのインデックスを返す。

（例）
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
理由：nums[0] + nums[1] == 9 であるので、Outputは[0,1]となる。

解法

Runtimeで66％、Memoryで36％の回答を上回った計算量$O^2$の解法を紹介する。
この問題は、targetとnumsリスト要素の差を前から順に求め、差をnumsリスト中から見つけること、そしてそのインデックスを求めることが出来れば解けそうだ。新しくdict型の変数を作りnumsの全要素を入れてしまいたくなるが、ここではそれをせず、下記のステップのイメージで解く。

1. dict型変数hashmapを定め、ハッシュマップを作る　
   1.　targetとnumsリストの値の差を前から順に求める
   2.　求めた差をhashmap中に探し、あればnums要素のインデックスを戻し、なければhashmapに当該nums要素を追加する

solution.py

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