Pythonで「良いトリプレット」の数を数えるプログラムの書き方

問題概要

配列 nums と、3つの異なる整数 a、b、c が与えられます。このとき、条件を満たす「良いトリプレット（good triplet）」の個数を求めるのが目的です。

トリプレット (nums[i], nums[j], nums[k]) が良いトリプレットとみなされるのは、以下の条件をすべて満たす場合です。

• 0 <= i < j < k < nums の要素数
• |nums[i] − nums[j]| <= a
• |nums[j] − nums[k]| <= b
• |nums[i] − nums[k]| <= c

たとえば、nums = [5,2,3,3,12,9]、a = 7、b = 2、c = 3 という入力の場合、出力は 4 になります。これは、(5,2,3)、(5,2,3)、(5,3,3)、(2,3,3) の4つの組み合わせが条件を満たすためです。

解法のアプローチ

この問題は、i < j < k を満たすすべてのインデックスの組み合わせを総当たり（ブルートフォース）で調べることで解けます。手順は以下の通りです。

• 結果を格納する変数 res を 0 で初期化する
• i を 0 から nums のサイズ − 1 までループさせる
• j を i+1 から nums のサイズ − 1 までループさせる
• k を j+1 から nums のサイズ − 1 までループさせる
• 3つの絶対値の条件をすべて満たしていれば、res を 1 増やす
• ループ終了後、res を返す

三重ループを使用するため、計算量は O(n³) となります。ただし、LeetCode の制約では配列の長さが最大100程度と小さいため、この単純な全探索でも十分に高速に動作します。

Pythonでの実装例

以下に実際のコードを示します。

def solve(nums, a, b, c):
    res = 0
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            for k in range(j+1, len(nums)):
                if abs(nums[i] - nums[j]) <= a and abs(nums[j] - nums[k]) <= b and abs(nums[i] - nums[k]) <= c:
                    res += 1
    return res

nums = [5,2,3,3,12,9]
a = 7
b = 2
c = 3
print(solve(nums, a, b, c))

入力

[5,2,3,3,12,9], 7, 2, 3

出力

4

まとめ

「良いトリプレット」の問題は、絶対値を使った3つの条件を理解し、ネストしたループですべての組み合わせを確認するだけで解決できます。アルゴリズム自体はシンプルですが、インデックスの順序制約（i < j < k）を正しく扱うことがポイントです。競技プログラミングやコーディング面接の練習として、ぜひ手を動かして試してみてください。