Pythonでリスト内の3つの異なる要素の合計がkと一致するか判定するプログラム

数値のリスト nums と値 k が与えられたとき、リストの中から合計が k と等しくなる3つの異なる要素を見つけられるかどうかを判定します。

たとえば、入力が nums = [11, 4, 6, 10, 5, 1]、k = 20 の場合、[4, 6, 10] の合計が 20 になるため、出力は True となります。

解法の考え方

この問題は、リストをソートしたうえで双方向ポインタ（two-pointer）を組み合わせることで、総当たりよりも効率的に解くことができます。手順は以下の通りです。

• リスト nums を昇順にソートする
• 左端を指す l = 0、右端を指す r = len(nums) - 1 として初期化する
• l < r - 1 の間、次の処理を繰り返す
  • 3つ目の候補となる値 t = k - nums[l] - nums[r] を計算する
  • nums[r - 1] < t の場合、それ以上大きな値は存在しないため l を1つ進めて次へ
  • m を l + 1 から r - 1 まで走査し、
    • nums[m] > t なら r を1つ減らして範囲を狭める
    • nums[m] == t なら True を返す
• 最後まで見つからなければ False を返す

実装例

理解を深めるために、実際のPythonコードを見てみましょう。

class Solution:
    def solve(self, nums, k):
        nums.sort()
        l, r = 0, len(nums) - 1
        while l < r - 1:
            t = k - nums[l] - nums[r]
            if nums[r - 1] < t:
                l += 1
                continue
            for m in range(l + 1, r):
                if nums[m] > t:
                    r -= 1
                    break
                if nums[m] == t:
                    return True
        return False

ob1 = Solution()
nums = [11, 4, 6, 10, 5, 1]
k = 20
print(ob1.solve(nums, k))

入力

[11, 4, 6, 10, 5, 1], 20

出力

True

計算量について

ソートに O(n log n)、その後の探索では左右のポインタが互いに近づきながら全体で O(n²) の処理となるため、すべての組み合わせを調べる O(n³) の素朴な手法よりも大幅に高速です。リストのサイズが大きい場合でも実用的に動作する点がこのアプローチの大きな利点といえます。