LeetCode「Two Sum」問題のPython解法と時間計算量の解説

はじめに

LeetCodeは、プログラミングスキルを磨くための人気プラットフォームです。今回の記事では、LeetCodeの定番問題である 「Two Sum」 をPythonで解いていきます。さらに、初心者がよく遭遇するエラーや効率的な実装の考え方も紹介します。

問題の概要

LeetCodeの「Two Sum」問題では、以下の条件に従って2つの数のインデックスを返すことが求められます。
https://leetcode.com/problems/two-sum/

問題の説明

• 整数の配列 nums と整数 target が与えられる。
• 配列内の2つの要素の和が target と等しくなるようなインデックスの組み合わせを探す。
• 1つの解が必ず存在することが保証されており、同じ要素を2回使うことはできない。
• インデックスの順序は問われない

クラスベースの実装と使用例

LeetCodeの多くの問題では、関数をクラス内に実装する形が求められます。そのため、今回の解法も Solution クラスにメソッドを実装する形にします。

実装例

class Solution:
    def twoSum(self, nums, target):
        # 数値とそのインデックスを保存する辞書
        num_to_index = {}

        # 配列の各要素を走査
        for i, num in enumerate(nums):
            # 補数 (target - 現在の要素) を計算
            complement = target - num

            # 補数が辞書に存在するか確認
            if complement in num_to_index:
                # 見つかった場合、解となるインデックスのペアを返す
                return [num_to_index[complement], i]

            # 現在の要素とそのインデックスを辞書に登録
            num_to_index[num] = i

# 使用例
solution = Solution()  # Solutionのインスタンスを生成
nums = [2, 7, 11, 15]
target = 9
result = solution.twoSum(nums, target)
print(result)  # 出力: [0, 1]

クラス実装の解説

1. Solutionクラス:
   twoSum メソッドをクラス内に定義します。この形式は、Pythonのオブジェクト指向プログラミング（OOP）に基づいています。
2. self引数:
   クラス内のメソッドでは、最初の引数に self を指定する必要があります。これは、インスタンスの状態を保持するためのものです。
3. メソッドの呼び出し:
   Solution クラスをインスタンス化し、そのインスタンスから twoSum() メソッドを呼び出します。ここでの solution = Solution() が重要なポイントです。

時間計算量の解説

このアルゴリズムの時間計算量は O(n) です。以下のように計算量が決まります。

1. ループの計算量
   配列 nums を1回走査するため、計算量は O(n) です。
2. 辞書操作の計算量
   辞書を使った要素の検索や追加は、平均的に O(1) の時間で行えます

O(n)の意味

O(n) とは、「入力サイズ n に比例して処理時間が増える」という意味です。たとえば、配列が10個の要素を持つときは約10回の操作が必要で、100個の場合は100回の操作が必要になります。

他の計算量との比較

• O(1): 定数時間（例: 配列の要素を1つ取得する）。
• O(n²): 二重ループで全ての組み合わせを探索する場合。
• O(log n): バイナリサーチのように、データを半分に分割する処理。

おわりに

LeetCodeの「Two Sum」問題では、辞書を使うことで O(n) の効率的なアルゴリズムを実現できます。さらに、クラスベースで実装することで、LeetCodeの環境に適応した解法が可能になります。