Pythonでターゲット値より大きいペアの最小合計を求める方法（二分探索・双方向ポインタ活用）

数値のリスト nums とターゲット値 target が与えられたとき、ターゲットより大きくなるペアの合計の中で最小のものを見つける問題を考えてみましょう。

例えば、入力が nums = [2, 4, 6, 10, 14]、target = 10 の場合、出力は 12 になります。これは、2 と 10 を選んだときの合計が 12 となり、ターゲット（10）を超えるペアの中で最も小さい合計だからです。

解法のアプローチ：双方向ポインタ（Two Pointers）

この問題は、リストをソートした上で「双方向ポインタ」というテクニックを使うと効率的に解けます。手順は以下の通りです。

• リスト nums を昇順にソートする
• n をリストのサイズとする
• answer を十分に大きい値（例：10^10）で初期化する
• 左ポインタ i = 0、右ポインタ j = n - 1 とする
• i < j の間、以下を繰り返す
  • nums[i] + nums[j] > target の場合：
    • answer を現在の合計と比較して小さい方に更新する
    • 右ポインタ j を 1 減らす（合計をさらに小さく試すため）
  • それ以外の場合：
    • 左ポインタ i を 1 増やす（合計を大きくする必要があるため）
• 最後に answer を返す

Pythonでの実装例

実際のコードを見てみましょう。

class Solution:
    def solve(self, nums, target):
        nums.sort()
        n = len(nums)
        answer = 10 ** 10
        i, j = 0, n - 1
        while i < j:
            if nums[i] + nums[j] > target:
                answer = min(answer, nums[i] + nums[j])
                j -= 1
            else:
                i += 1
        return answer

ob = Solution()
nums = [2, 4, 6, 10, 14]
target = 10
print(ob.solve(nums, target))

入力

[2, 4, 6, 10, 14], 10

出力

12

アルゴリズムのポイント

この手法の優れている点は、全てのペアの組み合わせを総当たり（O(n²)）で確認する必要がないことです。ソート済みのリストに対して左右からポインタを動かすことで、O(n log n)（ソートのコスト込み）という計算量で解けます。

• 合計がターゲットより大きい場合：そのペアは候補として記録し、右ポインタを左に動かして、より小さい合計を探します。左側の要素との組み合わせも考慮する必要があるため、右ポインタだけを動かせば十分です。
• 合計がターゲット以下の場合：右端の要素と組み合わせても条件を満たさないので、左ポインタを右に動かして合計を増やします。

これにより、各ステップで必ずどちらかのポインタが進むため、ループは最大 n-1 回で終了し、非常に効率的です。