【Python】K未満となる2数の和の最大値を求める方法

問題の概要

整数の配列 A と整数 K が与えられたとき、i < j を満たす組み合わせの中で、A[i] + A[j] = S かつ S < K となるような最大の S を求めます。条件を満たす i と j のペアが存在しない場合は -1 を返します。

たとえば、A = [34,23,1,24,75,33,54,8]、K = 60 の場合、34 と 24 を選ぶことで合計 58 が得られ、これは 60 未満です。他のどのペアよりも大きいため、出力は 58 となります。

解法のアプローチ

この問題は、すべてのペアを総当たりで確認するシンプルな手法で解くことができます。手順は以下の通りです。

• 答えを格納する変数 res = -1 で初期化します。
• 配列 A の要素が1つしかない場合は、-1 を返します。
• i を 0 から配列の長さまでループさせます。
  • j を i + 1 から配列の長さまでループさせます。
    • temp = A[i] + A[j] を計算します。
    • temp < K であれば、res = max(res, temp) で答えを更新します。
• 最後に res を返します。

この方法の計算量は O(n²) となり、配列のサイズがそれほど大きくない場合に有効です。

Pythonでの実装例

以下のコードで実際の実装を確認してみましょう。

class Solution(object):
   def twoSumLessThanK(self, A, K):
      ans = -1
      if len(A)==1:
         return -1
      for i in range(len(A)):
         for j in range(i+1,len(A)):
            temp = A[i]+ A[j]
            if temp<K:
               ans = max(ans,temp)
      return ans
ob1 = Solution()
print(ob1.twoSumLessThanK([34,23,1,24,75,33,54,8],60))

入力

[34,23,1,24,75,33,54,8]
60

出力

58

まとめ

この記事では、配列内の2つの要素を選んで K 未満となる最大の合計値を求める問題を Python で解きました。二重ループによる全ペアの探索は直感的で理解しやすい方法ですが、データ量が多い場合はソートと双方向ポインタ（Two Pointers）を組み合わせることで O(n log n) への高速化も可能です。まずは基本となる実装を理解したうえで、効率化の手法にも挑戦してみてください。