LoginSignup
0
0

LeetCode: Two Sum

Posted at

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
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0