LeetCodeを1日1題解いてみる (day1)

今日から毎日１題ずつLeetCodeの問題を解いていきます！

1. Two Sum (Easy)

問題文

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.

僕の回答

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = []
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    result.append(i)
                    result.append(j)
                    return result

より効率の良い回答例

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        map = dict()  # 空の辞書を初期化

        for index, value in enumerate(nums):
            if target - value in map: # mapにvalueの相方がいる場合
                if index <= map[target-value]:
                    return index, map[target-value] 
                else:
                    return map[target-value], index 
            else:
                map[value] = index # mapにindex, valueを追加

次回はこちら!