C#でターゲットに最も近い4つの数値の組み合わせ（四つ組）を見つける方法【Two Pointers活用】

問題の概要

「ターゲットに最も近い四つ組（4Sum Closest）」は、整数型の配列から4つの数値を選び、その合計が指定されたターゲット値にできるだけ近くなる組み合わせを探す古典的なアルゴリズム問題です。この問題は、Two Pointers（双方向ポインタ）パターンを応用した「四つ組の合計ゼロ（Quadruplet Sum to Zero）」と非常によく似ています。

解き方のアプローチ

基本的な流れは次のとおりです。

1. ソート：まず配列を昇順に並べ替えます。
2. 2つの数値を固定：二重ループで最初の2つの数値を1つずつ選んでいきます。
3. 残りをポインタで探索：残りの範囲に対して left（左端）と right（右端）の2つのポインタを用意し、4つの数値の合計を計算します。
4. 差を記録・比較：各ステップで「合計とターゲットの差の絶対値」を求め、これまでの最小差と比較しながら更新します。
5. 結果を返す：最終的に、差が最も小さかった組み合わせの合計を返します。

合計がターゲットより小さければ left を右へ、大きければ right を左へ動かすことで、効率的に候補を絞り込めるのがこのパターンのポイントです。

計算量

時間計算量

配列のソートに O(N * logN)、その後の三重ループによる探索に O(N^3) かかるため、全体の時間計算量は O(N * logN + N^3)、漸近的には O(N^3) と同等になります。

空間計算量

ソート済みの配列を保持するために追加の領域が必要となるため、空間計算量は O(N) です。

C#での実装例

using System;
using System.Linq;

public class Arrays {
    public int FourSumClosestToTarget(int[] nums, int target) {
        if (nums == null || nums.Length < 4) {
            return -1;
        }

        int[] sorted = nums.OrderBy(x => x).ToArray();

        // 初期値：先頭4要素の合計
        int closestSum = sorted[0] + sorted[1] + sorted[2] + sorted[3];
        int minDiff = Math.Abs(closestSum - target);

        // 最初の2つの数値を固定
        for (int i = 0; i < sorted.Length - 3; i++) {
            for (int j = i + 1; j < sorted.Length - 2; j++) {
                int left = j + 1;
                int right = sorted.Length - 1;

                // 残りの2つは左右ポインタで探索
                while (left < right) {
                    int currentSum = sorted[i] + sorted[j] + sorted[left] + sorted[right];
                    int diff = Math.Abs(currentSum - target);

                    // ターゲットとの差がより小さい場合は更新
                    if (diff < minDiff) {
                        minDiff = diff;
                        closestSum = currentSum;
                    }

                    if (currentSum == target) {
                        return currentSum;   // 完全一致なら即座に返す
                    } else if (currentSum < target) {
                        left++;              // 合計が小さい → 左ポインタを進める
                    } else {
                        right--;             // 合計が大きい → 右ポインタを戻す
                    }
                }
            }
        }
        return closestSum;
    }
}

class Program {
    static void Main(string[] args) {
        var s = new Arrays();
        int[] nums = { 1, 0, -1, 0, -2, 2 };
        int result = s.FourSumClosestToTarget(nums, 0);
        Console.WriteLine(result);
    }
}

コードのポイント

• 入力チェックとして、配列が null または要素数が4未満の場合は -1 を返します。
• LINQ の OrderBy でソートした新しい配列を作成し、元の配列は変更しません。
• closestSum（現在の最良の合計）と minDiff（ターゲットとの最小差）を管理することで、ターゲットが負の値の場合でも正しく動作します。
• 合計がターゲットと完全一致した時点で即座に返すため、無駄な探索を省けます。

実行結果

0

この例では、配列 { 1, 0, -1, 0, -2, 2 } の中から {-2, -1, 1, 2} を選ぶと合計がちょうど 0 になり、ターゲット値 0 と完全一致するため 0 が出力されます。

まとめ

ターゲットに最も近い四つ組を見つける問題は、「ソート ＋ 2要素の固定 ＋ Two Pointers」の組み合わせにより O(N^3) 時間で解くことができます。重要なのは、合計そのものではなく「ターゲットとの差」を追跡することです。このパターンは「3Sum Closest」など他の類似問題にもそのまま応用できるので、ぜひマスターしておきましょう。