Pythonでリストにピタゴラス数（三つ組）が存在するかチェックする方法

問題概要

nums という数値のリストが与えられたとき、次の等式を満たす3つの数 a、b、c が存在するかどうかを判定します。

a² + b² = c²

これはいわゆる「ピタゴラス数（三つ組）」の有無を確認する問題です。例えば、入力が [10, 2, 8, 5, 6] の場合、8² + 6² = 64 + 36 = 100 = 10² が成り立つため、出力は True になります。

解法のアプローチ

この問題は、全ての組み合わせを総当たりで調べることも可能ですが、降順ソート＋二ポインタ法を使うことでより効率的に解けます。全体の手順は以下の通りです。

1. nums 内のすべての数値を2乗し、降順にソートしたリスト tmp を作成します。
2. tmp 内の各インデックス i とその値 n に対して、以下を繰り返します。
   • base := n（斜辺の候補となる2乗の値）
   • left := i + 1、right := tmp のサイズ − 1 として初期化
   • left ≤ right の間、以下を繰り返します。
     • t := tmp[left] + tmp[right]
     • t == base の場合：True を返す（ピタゴラス数が見つかった）
     • t > base の場合：left を +1 して合計を小さくする
     • それ以外の場合：right を −1 して合計を大きくする
3. すべての探索が終わったら False を返します。

降順にソートされているため、ポインタの移動方向によって合計値を一意に制御できるのがこの手法のポイントです。

実装例

class Solution:
    def solve(self, nums):
        tmp = sorted([n*n for n in nums], reverse=True)
        for i, n in enumerate(tmp):
            base = n
            left = i + 1
            right = len(tmp) - 1
            while left <= right:
                t = tmp[left] + tmp[right]
                if t == base:
                    return True
                elif t > base:
                    left += 1
                else:
                    right -= 1
        return False

ob = Solution()
print(ob.solve([10, 2, 8, 5, 6]))

入力

[10, 2, 8, 5, 6]

出力

True

計算量について

各要素を斜辺候補として固定するのに O(n)、その後の二ポインタ探索に O(n) かかるため、全体の時間計算量は O(n²) となります。ソートに伴う空間計算量は O(n) です。総当たり（O(n³)）と比べて大幅に高速化できる点が、このアルゴリズムの大きな利点です。