Pythonで合計がkに等しい4つの異なる要素を見つけられるか判定するプログラム

問題の概要

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

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

解法のアプローチ:ソート + 双方向ポインタ法

この問題は、いわゆる「4Sum」問題と呼ばれるものです。全組み合わせを総当たりすると計算量が膨大になりますが、リストをソートしたうえで双方向ポインタ(two pointers)テクニックを使うことで、効率よく探索できます。

手順は以下の通りです。

• まずリスト nums をソートします。
• n := nums のサイズとします。
• i を 0 から n − 4 の範囲で繰り返します。
  • j を i + 1 から n − 3 の範囲で繰り返します。
    • l := j + 1、h := nums のサイズ − 1 とします。
      • l < h の間、以下を繰り返します。
        • summ := nums[i] + nums[j] + nums[l] + nums[h] を計算します。
        • summ == k なら True を返します。
        • summ < k なら l := l + 1(左ポインタを右へ移動)。
        • それ以外の場合は h := h − 1(右ポインタを左へ移動)。
• すべての候補を調べても見つからなければ False を返します。

ソートしておくことで、合計が小さすぎる場合は左端のポインタを進め、大きすぎる場合は右端のポインタを戻す、という操作で目的の合計値に近づけていくことができます。

実装例

それでは、実際のコードを見て理解を深めましょう。

class Solution:
    def solve(self, nums, k):
        nums.sort()
        n = len(nums)
        for i in range(n - 3):
            for j in range(i + 1, n - 2):
                l, h = j + 1, len(nums) - 1
                while l < h:
                    summ = nums[i] + nums[j] + nums[l] + nums[h]
                    if summ == k:
                        return True
                    elif summ < k:
                        l += 1
                    else:
                        h -= 1
        return False

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

入力

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

出力

True

計算量について

外側の2重ループ(i と j)に加えて、内側でポインタを動かしながら走査するため、全体の時間計算量は O(n³) となります。総当たり方式の O(n⁴) と比べると大幅に効率化されており、ソートのコスト O(n log n) を含めても十分に高速です。