問題概要

整数配列 numbers が与えられたとき、異なる3つの要素 numbers[i] + numbers[j] + numbers[k] == 0 を満たすすべての一意な三元組 (i, j, k) を見つけて返します。ただし、i, j, k はすべて異なるインデックスを指す必要があります。

制約条件

• 配列の長さ: 3 ≤ numbers.length ≤ 3000
• 要素の範囲: -10⁵ ≤ numbers[i] ≤ 10⁵

実行例

入力: numbers = [-1, 0, 1, 2, -1, -4]
出力: [[-1, -1, 2], [-1, 0, 1]]
説明: 和がゼロになる三元組は (-1, 0, 1) と (-1, -1, 2) の2つです。

解決策：ソートと双指针手法

この問題は効率的に解決するために、配列のソートと双指针テクニックを組み合わせるのが最適です。ハッシュマップを使用した単純な拡張では重複する結果を処理するのが困難です。

コアとなる考え方

1. 配列のソート: これにより、重複要素のスキップと指针の効率的な移動が可能になります
2. 基点の固定: 最初の要素をループで固定し、残りの2要素を双指针で探索
3. 重複排除: 各段階で重複する値を識別してスキップ
4. 早期終了: ソート済み配列の特性を利用して不要な探索を省略

実装コード（C#）

public class TripleSumSolver {
    public IList FindZeroSumTriplets(int[] data) {
        var solutions = new List();
        
        if (data == null || data.Length < 3) {
            return solutions;
        }
        
        Array.Sort(data);
        int arrayLength = data.Length;
        
        // 基点となる要素を走査
        for (int anchor = 0; anchor < arrayLength - 2; anchor++) {
            // 正の値から先は和がゼロになる可能性がない
            if (data[anchor] > 0) {
                break;
            }
            
            // 重複する基点をスキップ
            if (anchor > 0 && data[anchor] == data[anchor - 1]) {
                continue;
            }
            
            // 残りの範囲で双指针を使用
            int forward = anchor + 1;
            int backward = arrayLength - 1;
            
            while (forward < backward) {
                int currentSum = data[anchor] + data[forward] + data[backward];
                
                if (currentSum == 0) {
                    // 有効な三元組を発見
                    solutions.Add(new List<int> { data[anchor], data[forward], data[backward] });
                    
                    // 重複するforward値をスキップ
                    while (forward < backward && data[forward] == data[forward + 1]) {
                        forward++;
                    }
                    // 重複するbackward値をスキップ
                    while (forward < backward && data[backward] == data[backward - 1]) {
                        backward--;
                    }
                    
                    forward++;
                    backward--;
                }
                else if (currentSum < 0) {
                    // 和が小さすぎる場合、forwardを増加
                    forward++;
                }
                else {
                    // 和が大きすぎる場合、backwardを減少
                    backward--;
                }
            }
        }
        
        return solutions;
    }
}

コードの詳細解説

1. 初期化フェーズ

配列をソートすることで、要素が昇順に並び、指针の移動方向が明確になります。例えば [-4, -1, -1, 0, 1, 2] となり、重複する-1が隣接します。

2. 基点要素の処理

anchor 変数が最初の要素を担当します。data[anchor] > 0 のチェックは重要な最適化で、ソート済み配列では正の値に加えても和がゼロにならないため、ループを即座に終了できます。

3. 重複排除ロジック

基点レベルでは data[anchor] == data[anchor - 1] で重複を検出。双指针側では解発見後に while ループで同一値を一気にスキップします。これにより [-1, -1, -1, 2] などのケースで重複する結果を防ぎます。

4. 双指针の動作

forward 指针は左から右へ、backward 指针は右から左へ移動。currentSum が0未満なら forward++ で大きな値を追加、0より大きいなら backward-- で小さな値を追加します。

計算量分析

• 時間計算量: O(n²) - ソートが O(n log n)、基点の走査が O(n)、各基点に対する双指针探索が平均 O(n)
• 空間計算量: O(1) - 結果格納用のメモリを除けば追加の線形メモリを使用しない

高度な最適化テクニック

以下の条件チェックを追加することで、さらに実行時間を短縮できます：

// 現在のanchorに対する理論上の最小値と最大値を計算
int theoreticalMin = data[anchor] + data[anchor + 1] + data[anchor + 2];
int theoreticalMax = data[anchor] + data[arrayLength - 2] + data[arrayLength - 1];

if (theoreticalMin > 0) break;  // これ以上探索する意味がない
if (theoreticalMax < 0) continue; // 現在のanchorでは解なし

これにより、不必要な双指针探索を事前に排除できます。

エッジケースへの対応

• 全ゼロ配列: [0, 0, 0] → [[0, 0, 0]] を正しく返却
• 解なしケース: [0, 1, 1] → 空のリストを返却
• 最小サイズ: 3要素配列でも正しく動作
• 負の数のみ: 和がゼロにならないため空リストを返却