【LeetCodeに挑戦】1.Two Sum

現在ITエンジニアとして働いていますが、コーディング・アルゴリズム力をもっと鍛えたいと思い、LeetCodeで学んだ内容をメモ的にアウトプットしています。
今回解いてみた問題は「1. Two Sum」です。

問題

配列nums、目標値targetが与えられており、nums内の2要素を足してtargetとなるインデックスを求める。
同一要素を加算するのはなし。（難易度はEasy）

例

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

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

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

解法

1：全ループ

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n - 1):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []  # No solution found

2：ハッシュテーブル

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

学んだこと：アルゴリズム

• 解法1の総当たり（ブルートフォース）では、時間計算量がO(n2)、空間計算量は追加のデータ構造を使用しないためO(1)

• ハッシュテーブルは時間計算量がO(n)、空間計算量はハッシュマップで最大でn個の要素を格納するためO(1)。

学んだこと：英語

• 時間計算量：time complexity

• 空間計算量：space complexity

• インデックス：indices（indexの複数形）