C#で合計がゼロになるすべての一意のトリプレットを見つける方法

整数の配列が与えられたとき、「3つの要素の合計がゼロになる組み合わせ（トリプレット）」をすべて見つけ出すのは、アルゴリズムの定番問題の一つです。この記事では、単純な総当たり法から効率的な「ソート＋双方向ポインタ」方式まで、複数のアプローチとその計算量、C#での実装例をわかりやすく解説します。

アプローチ1：三重ループによる総当たり（ブルートフォース）

最もシンプルな方法は、3つのネストしたループを作成し、すべての要素の組み合わせについて合計がゼロかどうかを一つずつ確認するやり方です。合計がゼロになった場合は、その3つの要素を出力します。

時間計算量： O(n³)
空間計算量： O(1)

この方法は実装が簡単ですが、データ量が増えると処理時間が急激に伸びるため、実用的とは言えません。

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

次に、HashSet（順序なし集合）を使って配列の各値を格納する方法があります。セットは要素の検索をO(1)の時間で行えるという利点があります。そのため、配列内の各ペアに対して、「そのペアの合計の符号を反転した値」がセット内に存在するかどうかを調べます。該当する要素が見つかれば、そのペアと合計の反転値の3つ組が答えとなります。

時間計算量： O(n²)
空間計算量： O(n)

総当たり法より大幅に高速化できますが、追加のメモリが必要になる点に注意しましょう。

アプローチ3：ソート＋双方向ポインタ（Two Pointers）

最も効率的かつ定番とされるのが、この手法です。まず配列を昇順にソートし、固定した1つの要素に対して、残りの範囲の左右両端からポインタを移動させながら合計を評価します。

• 合計がゼロなら、そのトリプレットを結果に追加し、重複を避けるために同じ値のポインタをスキップします。
• 合計が負なら、左ポインタを右へ進めて合計を大きくします。
• 合計が正なら、右ポインタを左へ進めて合計を小さくします。

この方法なら、時間計算量 O(n²)・空間計算量 O(1)（ソート領域を除く）で、しかも重複するトリプレットを自動的に排除できます。

C#での実装例

public class Arrays {
    public List<List<int>> ThreeSum(int[] nums) {
        List<List<int>> res = new List<List<int>>();
        if (nums == null || nums.Length == 0) {
            return res;
        }
        // 配列を昇順にソート
        var sorted = nums.OrderBy(x => x).ToArray();
        for (int i = 0; i < sorted.Length; i++) {
            int left = i + 1;
            int right = sorted.Length - 1;
            while (left < right) {
                int sum = sorted[i] + sorted[left] + sorted[right];
                if (sum == 0) {
                    res.Add(new List<int> { sorted[i], sorted[left], sorted[right] });
                    // 重複する値をスキップ
                    int leftValue = sorted[left];
                    while (left < sorted.Length && leftValue == sorted[left]) {
                        left++;
                    }
                    int rightValue = sorted[right];
                    while (right > left && rightValue == sorted[right]) {
                        right--;
                    }
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
            // 基準となる要素の重複もスキップ
            while (i + 1 < sorted.Length && sorted[i] == sorted[i + 1]) {
                i++;
            }
        }
        return res;
    }
}

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

実行結果

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

まとめ

入力 { -1, 0, 1, 2, -1, -4 } の場合、合計がゼロになる一意のトリプレットとして [-1,-1,2] と [-1,0,1] の2つが得られます。単純な三重ループではO(n³)かかる処理も、ソートと双方向ポインタを組み合わせることでO(n²)まで高速化でき、重複排除も同時に実現できます。面接やコーディングテストでも頻出のテクニックなので、ぜひマスターしておきましょう。