Problem
リスト nums と特定の値 target が与えられ、nums の2つの要素を合計するとtargetになる要素のindexを返すという問題です。
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
InputとOutputの例は次になります。
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Key Idea
返す値がindexというのがポイントになります。"補数"（targetから現在の数を引いたもの）が既にリストの以前の部分に存在するかどうかを確認します。
リストで走査した値の管理には、Hashtable(PythonではDictionary)を使います。
Approach #1 : Brute Force
まずは、Brute Force 手法を記載します。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
この解法では、計算量は下記の様になります。
-
Time complexity: O(n^2)。二重ループを使っています。ここで、nは
numsの要素数です。 -
Space complexity: O(1)。必要なメモリは、
numsの長さに依存しません。
Approach #2 : Hashmap
Key Ideaで言及した、補数とHashmapを利用した方法です。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
d = {}
for i, num in enumerate(nums):
complement = target - num
if complement in d:
return [d[complement], i]
else:
d[num] = i
この解法では、計算量は下記の様になります。
-
Time complexity: O(n)。リスト全体を1回しか走査しないためです。
-
Space complexity: O(n)。最悪の場合、すべての要素をハッシュテーブルに保存する必要があります。