【Python】リスト内に「数値とその3倍」のペアが存在するか判定するアルゴリズム

問題の概要

数値のリスト nums が与えられたとき、その中に「一方の数がもう一方の数のちょうど3倍」となっているペアが存在するかどうかを判定します。

たとえば、入力が nums = [2, 3, 10, 7, 9] の場合を考えてみましょう。このリストには 3 と、その3倍である 9 が含まれているため、出力は True になります。

解き方の考え方

この問題は、リストをあらかじめソートしておき、2つのポインタを使って走査することで効率的に解けます。ある数の3倍は必ず元の数よりも大きいため、昇順に並べたリストに対して前方向きにポインタを動かせばよいのがポイントです。

• ポインタ i を 0 に初期化する
• リスト n を昇順にソートする
• ポインタ j を 1 に初期化する
• j がリストの長さ未満である限り、以下を繰り返す:
  • 3 × n[i] が n[j] と一致すれば、True を返す
  • 3 × n[i] が n[j] より大きければ、j を 1 進める
  • それ以外の場合は、i を 1 進める
• ループが終了したら、該当するペアは存在しないので False を返す

この手法では、ソートに O(n log n)、ペアの探索には各ポインタが最大でもリスト長分しか進まないため O(n) で処理でき、すべての組み合わせを総当たりする非効率な方法を避けられます。

実装例

それでは、実際のPythonコードを見てみましょう。

class Solution:
    def solve(self, n):
        i = 0
        n.sort()
        j = 1
        while (j < len(n)):
            if (3*n[i] == n[j]):
                return True
            if (3*n[i] > n[j]):
                j += 1
            else:
                i += 1
        return False

ob = Solution()
print(ob.solve([2, 3, 10, 7, 9]))

入力

[2, 3, 10, 7, 9]

出力

True

まとめ

リストをソートしてから2つのポインタを併用することで、「一方が他方の3倍」という条件を満たす数値のペアの有無を効率的に判定できます。ソート済みデータに対する探索系の問題では定番となるテクニックなので、覚えておくとさまざまな場面で応用できます。