Pythonでターゲット未満となる最大のペア合計を求めるプログラム

問題の概要

数値のリスト nums とターゲット値 target が与えられたとします。このとき、合計がターゲット未満(target - 1 以下)となる2つの数値のペアの中から、最も大きな合計を見つける必要があります。

たとえば、入力が nums = [8, 3, 4, 9, 2]、target = 8 の場合、出力は 7 になります。これは、8 未満となる最大のペアの合計が 4 + 3 = 7 だからです。

解法のアプローチ

この問題は「ソート + 両端ポインタ(ツーポインタ法)」というテクニックを使うことで効率的に解けます。手順は以下のとおりです。

• リスト nums を昇順にソートします。
• 左ポインタ p1 を 0、右ポインタ p2 をリストの末尾(サイズ − 1)に設定します。
• 変数 m を負の無限大(-inf)で初期化します。
• p1 < p2 の間、以下を繰り返します。
  • nums[p1] + nums[p2] < target の場合:m を現在の合計と比較して大きい方で更新し、p1 を1つ右へ進めます。
  • それ以外の場合:合計がターゲット以上なので、p2 を1つ左へ戻します。
• ループ終了後、m を返します。

なぜこの方法が機能するのか

リストを事前にソートしておけば、両端から挟み込むように合計を調べることで、すべてのペアを総当たり(O(n²))せずとも最適な組み合わせを効率よく見つけられます。合計がターゲット以上なら右側の値を下げて合計を減らし、ターゲット未満ならその合計を候補として記録したうえで左側の値を上げていきます。

実装例

以下はPythonでの実装例です。

import math

def solve(nums, target):
    nums.sort()
    p1 = 0
    p2 = len(nums) - 1
    m = -math.inf
    while p1 < p2:
        if nums[p1] + nums[p2] < target:
            m = max(m, nums[p1] + nums[p2])
            p1 += 1
        else:
            p2 -= 1
    return m

nums = [8, 3, 4, 9, 2]
target = 8
print(solve(nums, target))

入力

[8, 3, 4, 9, 2], 8

出力

7

計算量

ソートに O(n log n)、その後のポインタ走査に O(n) かかるため、全体の時間計算量は O(n log n) です。追加で必要なメモリは定数領域のみで済むため、非常に効率的な解法といえます。