【Python】2つのペアの合計差が最小になる数値の組み合わせを見つけるプログラム

問題の概要

数値のリスト nums が与えられたとき、その中から2組の数値ペアを選び、それぞれのペアの合計値の絶対差が最小になるような組み合わせを求めたいとします。

例えば、入力が nums = [3, 4, 5, 10, 7] の場合、出力は 1 になります。これは、(3 + 7) と (4 + 5) という2組のペアを選ぶことで、(3 + 7) - (4 + 5) = 1 という最小の差が得られるためです。

解決のためのアルゴリズム

この問題は、以下の手順に従って解くことができます。

• 空のリスト distances を用意します。
• i を 0 から nums のサイズ - 2 まで繰り返します。
  • j を i + 1 から nums のサイズ - 1 まで繰り返します。
    • distances の末尾に [|nums[i] - nums[j]|, i, j] を追加します。
• リスト distances を昇順にソートします。
• ans := 10^9（十分に大きい初期値）とします。
• i を 0 から distances のサイズ - 2 まで繰り返します。
  • [dist, i1, i2] := distances[i]
  • j := i + 1
  • [dist2, i3, i4] := distances[j]
  • j < distances のサイズ かつ (i1, i2, i3, i4) の要素がすべて一意でない間、次を繰り返します。
    • [dist2, i3, i4] := distances[j]
    • j := j + 1
  • (i1, i2, i3, i4) の要素がすべて一意（＝同じ要素を含まない4つの異なるインデックス）である場合、
    • ans := ans と (dist2 - dist) の最小値
• 最後に ans を返します。

サンプルコード

理解を深めるために、以下のPython実装を見てみましょう。

class Solution:
   def solve(self, nums):
      distances = []
      for i in range(len(nums) - 1):
         for j in range(i + 1, len(nums)):
            distances.append((abs(nums[i] - nums[j]), i, j))
      distances.sort()
      ans = 1e9
      for i in range(len(distances) - 1):
         dist, i1, i2 = distances[i]
         j = i + 1
         dist2, i3, i4 = distances[j]
         while j < len(distances) and len({i1, i2, i3, i4}) != 4:
            dist2, i3, i4 = distances[j]
            j += 1
         if len({i1, i2, i3, i4}) == 4:
            ans = min(ans, dist2 - dist)
      return ans

ob = Solution()
nums = [3, 4, 5, 10, 7]
print(ob.solve(nums))

入力

[3, 4, 5, 10, 7]

出力

1

コードのポイント

このアルゴリズムの鍵となるのは、すべてのペアについて「合計値の差」ではなく「要素の差」を事前に計算してソートしておく点です。ソート済みのリスト上で隣接する候補同士を比較することで、合計差が最小になりうる組み合わせを効率よく探索できます。

また、set を使って {i1, i2, i3, i4} のサイズが 4 になっているかどうかを確認することで、選んだ2つのペアが同じ要素（インデックス）を共有していないことを保証しています。これにより、各数値が重複して使われることのない正しいペアの組み合わせだけが評価されます。