[LeetCode] 1. Two Sum

問題

https://leetcode.com/problems/two-sum/description/

解答と解説

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        numMap = {}
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in numMap:
                # 制約上1つ以上のペアは必ず存在するのでここのreturnのみでOK
                return [i, numMap[complement]]
            numMap[nums[i]] = i

numsの要素数をnとした時、

• Time Complexity: O(n)
• Space Complexity: O(n)

全探索だとO(n^2)かかる処理をhashMapを使うことでO(n)で処理できるという有名な問題。

targetと同じ和になるペアがある = 補数が存在する、という変換ができるかがポイント。