【C#】合計がゼロになる一意な4つ組（4Sum）をすべて見つける方法

整数の配列から、合計がゼロになる重複のない4つの要素の組み合わせ（4つ組）をすべて見つける問題は、コーディング面接で頻出する古典的なアルゴリズム課題です。本記事では、単純な全探索からハッシュセットを利用する方法、さらに実用的な「ソート＋ツーポインタ」による効率的な解法まで、段階的に解説します。

アプローチ1：4重ループによる全探索

最も簡単な方法は、4つのネストしたループを作成し、選んだ4つの要素の合計がゼロかどうかを1つずつ確認することです。合計がゼロになれば、その組み合わせを出力します。

時間計算量 − O(n⁴)

空間計算量 − O(1)

アプローチ2：ハッシュセットを活用する

配列の各値をハッシュセット（HashSet）に格納しておけば、要素の検索をO(1)時間で行えます。そこで、配列内の各ペアについて「ペアの合計の符号を反転した値」がセット内に存在するかを調べます。該当する値が見つかれば、そのペアと反転値を組み合わせた4つ組として出力できます。

時間計算量 − O(n³)

空間計算量 − O(n)

推奨解法：ソート＋ツーポインタ

より効率的で一般的なのが、次の手順です。

• 配列を昇順にソートする。
• 外側の2重ループで最初の2つの要素（i、j）を固定する。
• 残りの範囲に対して左端（left）と右端（right）のポインタを用意し、合計がゼロになるよう互いを近づけていく。
• 同じ値の連続はスキップすることで、重複する組み合わせを排除する。

この手法なら、O(n³)の時間計算量を保ちながら、追加のメモリをほとんど使わずに一意な4つ組を列挙できます。

C#での実装例

using System;
using System.Collections.Generic;
using System.Linq;

public class Arrays {
    public List<List<int>> FourSum(int[] nums) {
        List<List<int>> res = new List<List<int>>();
        if (nums == null || nums.Length < 4) {
            return res;
        }
        int[] newNums = nums.OrderBy(x => x).ToArray();
        int n = newNums.Length;
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && newNums[i] == newNums[i - 1]) continue; // 重複スキップ
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && newNums[j] == newNums[j - 1]) continue; // 重複スキップ
                int left = j + 1;
                int right = n - 1;
                while (left < right) {
                    int sum = newNums[i] + newNums[j] + newNums[left] + newNums[right];
                    if (sum == 0) {
                        res.Add(new List<int> { newNums[i], newNums[j], newNums[left], newNums[right] });
                        int leftValue = newNums[left];
                        int rightValue = newNums[right];
                        while (left < right && newNums[left] == leftValue) left++;
                        while (left < right && newNums[right] == rightValue) right--;
                    } else if (sum < 0) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return res;
    }
}

class Program {
    static void Main(string[] args) {
        Arrays s = new Arrays();
        int[] nums = { 1, 0, -1, 0, -2, 2 };
        var result = s.FourSum(nums);
        foreach (var quad in result) {
            Console.WriteLine("[" + string.Join(",", quad) + "]");
        }
    }
}

出力結果

[-2,-1,1,2]
[-2,0,0,2]
[-1,0,0,1]

まとめ

入力例 { 1, 0, -1, 0, -2, 2 } の場合、合計がゼロになる一意な4つ組は [-2,-1,1,2]、[-2,0,0,2]、[-1,0,0,1] の3通りです。4重ループによる全探索は理解しやすいもののO(n⁴)と非効率なため、実践ではソートとツーポインタを組み合わせたO(n³)の解法を採用するのがおすすめです。