【C++】ターゲットに最も近い3つの数の合計を求めるアルゴリズム

問題の概要

n個の整数を含む配列 nums と、1つのターゲット値 target が与えられます。この中から3つの整数を選び、その合計がターゲットに最も近くなるような組み合わせを見つけ、その合計値を返すことが目的です。なお、各入力には必ず解が1つだけ存在すると仮定してよいものとします。

例えば、配列が [-1, 2, 1, -4]、ターゲットが 1 の場合、最適な組み合わせは [-1, 2, 1] で、その合計は 2 となります。これがターゲットに最も近い合計値です。

解法のアプローチ

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

• 配列 nums をソートし、答えを格納する変数 ans を 0、最小差分 diff を無限大（INT_MAX）、要素数 n をそれぞれ初期化する
• i を 0 から n−1 までループさせる
  • left := i + 1、right := n − 1 として設定する
  • left < right の間、以下を繰り返す
    • temp := nums[left] + nums[right] + nums[i] を計算する
    • |target − temp| が diff より小さければ、ans := temp、diff := |target − temp| に更新する
    • temp が target と一致すれば即座に temp を返す。temp > target なら right を1減らし、そうでなければ left を1増やす
• ループ終了後、ans を返す

この手法により、すべての組み合わせを総当たりする O(n³) の計算量を、O(n²) まで大幅に削減できます。

C++での実装例

以下に実際のC++コードを示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        int diff = INT_MAX;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            int left = i + 1;
            int right = n - 1;
            while(left < right){
                 int temp = nums[left] + nums[right] + nums[i];
                 if(abs(target - temp) < diff){
                     ans = temp;
                     diff = abs(target - temp);
                 }
                 if(temp == target)return temp;
                 else if(temp > target) right--;
                 else left++;
            }
        }
        return ans;
    }
};
main(){
    Solution ob;
    vector<int> v = {-1,2,1,-4};
    cout << ob.threeSumClosest(v, 1);
}

入力例

[-1,2,1,-4]
1

出力例

2

計算量の分析

時間計算量：O(n²) — 外側のループで1点を固定し、内側で双方向ポインタによる線形走査を行うためです。

空間計算量：O(1) — 追加のデータ構造を使用せず、定数個の変数のみで処理が完結するためです。