Pythonで合計がkに最も近い3つの異なる要素をリストから見つけるプログラム

この記事では、数値のリスト nums ともう一つの値 k が与えられたとき、|a + b + c − k| が最小になるようにリスト内の3つの異なる要素 (a, b, c) を選び、その絶対差を返す方法を解説します。

問題の例

たとえば、入力が nums = [2, 5, 25, 6]、k = 14 だった場合を考えてみましょう。[2, 5, 6] を選ぶと合計は13になり、14に最も近づきます。したがって絶対差は |13 − 14| = 1 となり、出力は 1 です。

解法のアプローチ(二ポインタ法)

この問題は、ソートと「二ポインタ」テクニックを組み合わせることで効率的に解けます。手順は以下の通りです。

• リスト nums を昇順にソートする
• ans を十分大きな値(109)で初期化する
• i を 0 から len(nums) - 1 までループさせる
  • 左ポインタ j := i + 1
  • 右ポインタ k := len(nums) - 1
  • j < k の間、以下を繰り返す
    • s := nums[i] + nums[j] + nums[k] を計算する
    • s <= target の場合:ans を min(ans, target − s) で更新し、j += 1 として合計を大きくする方向へ進む
    • それ以外の場合:ans を min(ans, s − target) で更新し、k -= 1 として合計を小さくする方向へ進む
• 最後に ans を返す

この手法により、全組み合わせを総当たり(O(n³))する必要がなくなり、時間計算量は O(n²) に抑えられます。

実装例(Pythonコード)

class Solution:
   def solve(self, nums, target):
      nums.sort()
      ans = 1e9
      for i in range(len(nums)):
         j = i + 1
         k = len(nums) − 1
         while j < k:
            s = nums[i] + nums[j] + nums[k]
            if s <= target:
               ans = min(ans, target - s)
               j += 1
            else:
               ans = min(ans, s - target)
               k −= 1
      return ans

ob1 = Solution()
nums = [2, 5, 25, 6]
k = 14
print(ob1.solve(nums, k))

入力

[2, 5, 25, 6], 14

出力

1

まとめ

リストをソートしてから固定の1要素に対して残りの範囲を左右のポインタで挟み込むことで、目的の合計に近づける要素の組み合わせを効率よく探索できます。目標値より合計が小さい場合は左ポインタを、大きい場合は右ポインタを動かすというシンプルな判断だけで、最適解に到達できるのがこのアルゴリズムのポイントです。