LeetCode備忘録_その4_Two Sum

概要

• LeetCodeを始めました。１テーマごとに解法と学びをメモします
• 今回テーマは「Arrays & Two Sum」

テーマ詳細

原文

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

- 2 <= nums.length <= 10^{4}

- 10^{-9} <= nums[i] <= 10{9} 

10^{-9}<= target <= 10^{9}

日本語訳

※G翻訳
整数 nums の配列と整数ターゲットを指定して、合計がターゲットになるような 2 つの数値のインデックスを返します。 各入力にはソリューションが 1 つだけ存在し、同じ要素を 2 回使用することはできないと想定できます。 回答は任意の順序で返すことができます。
例 1:

入力: nums = [2,7,11,15]、ターゲット = 9, 出力: [0,1]
説明: nums[0] nums[1] == 9 であるため、[0, 1] を返します。

例 2:

入力: nums = [3,2,4]、ターゲット = 6 出力: [1,2]

例 3:

入力: nums = [3,3]、ターゲット = 6 出力: [0,1]

制約:

- 2 <= nums.length <= 10^{4}

- 10^{-9} <= nums[i] <= 10{9} 

10^{-9}<= target <= 10^{9}

解法

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        numMap = {}
        n = len(nums)
        for i in range(n):
            complement = target - nums[i]
            if complement in numMap:
                return [numMap[complement], i]
            numMap[nums[i]] = i

        return []  # No solution found

結果

• Runtime:58ms
• Beats 89.29% of users with Python 　※投稿日時点

思想

• numsの中から、足してtargetになる"2つ"の数字の要素位置を返せば良いので、なにか工夫できそうだと感じる
• numsの頭から　target - nums[i]　を求めてnums[i+1:]にその値と一致するものがあるかどうかを判定すれば良さそう

学び

• for文の中で要素を記憶して置く方法として、for文の外で辞書を作っておいて、forループごとに辞書登録する
• リストではなく辞書にすることで、索引の処理を軽くする
• キーに要素、バリューに位置を持たせることで簡単に位置と要素を取り出せるようにする

感想

• 今回は今までの中で一番時間がかかった
• for文を使ってしまったが、使わない方法があれば知りたい。いくつか他の方のSolutionを見てみたがなかった